arrays - 最长递增的连续序列，其中开始元素大于结束元素 div 2

Question

我有一个排序数组，我想有效地找到从头到尾最长的连续子序列，如 array[begin]>=array[end] div 2。

显而易见的是 (O^(n^2) )，但还有更好的吗？

Answer 1

它可以在线性时间内完成。首先让我们从二次开始:

1. 从索引为 i 的第一个位置开始
2. 放入索引 j在索引i+1的位置
3. 只要未到达数组末尾且元素a[j]/2 <= a[i] , 递增 j
4. 记录索引的“分数”i .
5. 递增索引 i 并返回步骤 2。
6. 当所有指标都被覆盖后，取得分最高的指标。

要注意的是，如果您在第 3 步中失败了一对 (i, j) , 那么它的意思是:

for every i < k < j, a[k] <= a[i]/2
a[j] > a[i]/2

因此，在第 5 步，转到任何 k小于 j会导致分数变小，因为a[j] > a[i]/2 > a[k]/2 .因此，下一个开始的索引是 j .

现在我们在计算任何分数时最多访问一个索引一次。这从 O(n^2) 减少了这一步至 O(n) .然后取最高分的索引显然是O(n) .