arrays - 数组练习

Question

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

我正在考虑使用

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

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

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

Answer 1

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

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

但是，如果您以某种方式知道序列的平均长度相对较小，那么用线性搜索代替第二个二分搜索就开始有意义了. (这与合并两个长度相似的排序序列时的工作原理相同:线性搜索优于二分搜索，因为输入的结构保证平均搜索目标位于靠近序列开头的位置)。

更正式地说，如果整个数组的长度是n并且数组中不同整数值的个数(variety metric)是k，那么线性搜索就开始了当 n/k 变得小于 log2(n) 时平均优于二进制搜索(可能需要一些依赖于实现的常数因子来得出实际关系)。

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

但这需要有关输入数组属性的额外知识:我们需要知道 k。

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

由于数字是连续的，所以数组中的最后一个值减去数组中的第一个值等于k-1，也就是说

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

此规则也可以应用于原始数组的任何子数组，以计算该子数组的多样性指标。

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

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