0

我试图解决这个问题：给定一个包含从 0 开始的连续整数的排序数组（一个整数可能重复多次）例如 - （也可以很长 - 这只是一个例子），有效地找到开始和结束索引给定整数。0,0,0,1,2,3,3,3,4,4

我正在考虑使用

1）遍历（复杂度= O(n)）

2) 修改后的二分查找（复杂度 = O(log n)）。[ n = 总数组的长度]

然后想知道是否可以利用连续整数属性来解决它。有什么不同的想法或建议吗？

4

4 回答 4

1

您可以查看开始和结束元素以查看数组中有多少个元素k，然后对每个边界进行修改后的二进制搜索，检查元素及其左右。我认为你不能比 O( k log( n )) 更快。

如果您按从左到右（或从右到左）的顺序搜索边界，则应该减少平均时间，因为您可以在数组的较小子集中进行搜索，但我认为这不会影响最坏的情况-案件复杂性。

即检查索引i及其相邻元素，搜索 0-1 边界：

|0|0|0|1|1|1|1|1|2|2|2
         \ 一世 /

然后向左走：

|0|0|0|1|1|1|1|1|2|2|2
   \ 一世 /

既然你找到了它，现在在它右边的集合中寻找 1 和 2 之间的边界：

1|1|1|1|1|2|2|2
    \ 一世 /

1|1|1|1|1|2|2|2
        \ 一世 /

你已经完成了，因为你知道你正在寻找多少边界。

编辑：对不起，我没有意识到你只想要一个边界。过程类似——您找到要搜索的元素（即 O(log( n )) ），然后使用相同的修改后的搜索向左和向右搜索以检查边界。根据数组的整体大小与数组中的项目数，实际上只检查一侧或另一侧可能会更快。

于 2012-07-06T17:48:21.490 回答
1

首先，让我们忽略“连续性”属性

只要问题是找到处理单个请求的最有效方法，直接的通用解决方案就是执行两次连续的二进制搜索：第一个找到序列的开头，第二个找到序列的结尾顺序。第二次搜索在数组的剩余部分中执行，即在先前找到的序列开头的右侧。

但是，如果您以某种方式知道序列的平均长度相对较小，那么将第二次二进制搜索替换为线性搜索就开始有意义了。（这与合并两个相似长度的排序序列时的原理相同：线性搜索优于二分搜索，因为输入的结构保证平均搜索目标位于序列开头附近）。

更正式地说，如果整个数组的长度是并且数组n中不同整数值的数量（多样性度量）是需要提出一个实际的关系）。kn/klog2(n)

说明这种影响的极端例子是当 时的情况n=k，即当数组中的所有值都不同时。显然，使用线性搜索找到每个序列的结尾（一旦你知道开始）将比使用二分搜索更有效。

但这需要额外了解输入数组的属性：我们需要知道k.

这就是您的“连续性”属性发挥作用的时候！

由于数字是连续的，因此数组中的最后一个值减去数组中的第一个值等于k-1，这意味着

k = array[n-1] - array[0] + 1

此规则也可以应用于原始数组的任何子数组，以计算该子数组的品种度量。

这已经为您提供了一种非常可行且高效的序列查找算法：首先对序列的开头执行二进制搜索，然后根据和之间的关系（或者更好的是，长度之间的关系）执行二进制或线性搜索右子数组的数量和右子数组的多样性度量）。nk

PS 同样的技术也可以应用于第一次搜索。如果您正在寻找 的序列i，那么您会立即知道它是j数组中的第 - 个序列，其中j = i - array[0]。这意味着对该序列开头的线性搜索将j * n/k平均采取步骤。如果该值小于log2(n)，则线性搜索可能比二分搜索更好。

于 2012-07-06T18:21:42.717 回答
0

您的数组已排序，因此您可以使用二分搜索。说n是数组的大小，如果 n 是奇数，则将AA 除以大小 (n/2) 或分别为 (n/2) 和 (n/2) + 1。您正在寻找 j 的起始索引。(j 在 A 中)A1A2

 1. if A1(n/2) < j, then you know that j is in A2. 
 2. if A2(1) > j, then you know that j is in A1. 
 3. If A2(1) = j, then j may be in A1 and A2. Just check A1(n/2).
     if A1(n/2) < j then 2. Do the same recursively on A2 to find the last index
     else apply dichotomic search to find the starting index and ending index in both arrays
于 2012-07-06T18:03:41.707 回答
0

它必须是一个算法吗？你的问题只是说找到位置，但如果它确实是某种形式的算法方法，请告诉我，因为我提供了一个 PHP 函数，它以相当标准的方式处理这个问题。

$numbers = array(0,0,0,1,2,3,3,4,4,4,4);
function get_boundaries($array,$number)
{
    $keys = array_keys($array,$number);
    $found = count($keys);
    if($found == 0)
    {
        $ret = false;
    }
    else if($found == 1)
    {
        $ret = array($keys[0],$keys[0]);
    }
    else if($found > 1)
    {
        $ret = array($keys[0],$keys[$found-1]);
    }
    return $ret;
}

$result = get_boundaries($numbers,1);
print_r($result);


//Result when looking for 0
Array
(
    [0] => 0
    [1] => 2
)

//Result when looking for 1
Array
(
    [0] => 3
    [1] => 3
)

//Result when looking for 9
(boolean) false
于 2012-07-06T18:43:59.353 回答