数组练习

Question

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

我在考虑用

1)遍历(复杂性= O(n))

2)改进的二进制搜索(复杂度=O(log n))。N=总数组长度

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

Answer 1

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

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

然而，如果你知道序列的平均长度相对较小，那么用线性搜索代替第二个二进制搜索就开始有意义了。(这与合并两个长度相似的排序序列的原理相同:线性搜索优于二进制搜索，因为输入的结构保证搜索的目标平均位于序列的开头附近)。

更正式地说，如果整个数组的长度为n，数组中的不同整数值的数目(变化度量)为k，则当n/k小于log2(n)时，线性搜索的平均性能开始优于二进制搜索(可能需要一些依赖于实现的常数因子来建立实际关系)。

说明这种效果的极端例子是当n=k，即数组中的所有值都不同时的情况。显然，使用线性搜索来查找每个序列的结尾(一旦知道开始)将比使用二进制搜索效率高得多。

但是这需要对输入数组的属性有额外的了解:我们需要知道k。

这就是你的“连续性”财产开始发挥作用的时候！

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

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

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

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

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

Answer 2

您的数组是排序的，所以您可以使用二分搜索。假设n是数组A的大小，如果n是奇数，则在A1和A2中将A除以大小(n/2)或(n/2)和(n/2) +1。你在寻找j的起始指数。(j在A中)

 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

Answer 3

一定要用算法吗？您的问题只是说找到位置，但是如果它确实是某种形式的算法方法，请让我知道，因为我已经提供了一个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