我有一个问题:
我们有一个整数数组(大小为 n)[x_1,x_2,...,x_n]
我们必须找到最长的公共(public)部分 [x_i,x_i+1,...,x_j]
(x_i,x_i+1,...,x_j) 的最小值>= j-i+1
f.e [2,2,1,4,3,3,1] -> 3
(最长的正确部分是4,3, 3
)
我不知道如何将时间减少到 O(n^2)
以下(检查每个片段)
我的第二个想法是:每个值 x_k
都等于该部分可能具有的“长度范围”,如果数字较小,则我们更改“长度范围”(同时计算这有多长段),但我不知道如果我们得到更多的数字该怎么办
(我真的很感谢任何帮助 - 可能还有另一个更简单的解决方案,但我没有看到)
最佳答案
Caterpillar 方法,O(n),假设所有整数都是正数:
- 将左右指针放在第一个数字上,你的最小值 = 这个数字。长度 = 1
- 将右指针前进一位,检查条件(你很容易知道是否有新的最小值,并且你知道长度 += 1)
- 如果您不能在不破坏条件的情况下推进右指针,则推进左指针并更新您的值
- 如果左指针也不能前进,则说明找到了满足条件的节。注意它的长度,并在下一个索引上以同样的方式开始一个新的部分。
给你的例子:
[2,2,1,4,3,3,1]
[2] <- The first 2
[2,2] <- Moved the right
[2] <- Moved the left, both R and L are pointing at the second 2
<-Can't move either, note max length and indices from previous run.
[1] <- Starting again
<-Can't move either
[4] <- Starting again
[4,3] <- Right
[4,3,3] <- Right (New max length and indices noted)
[3,3] <- Left. Doesn't improve the max
[3] <- Left again.
<- Can't move either, note max and indices, in this case overwrite length
[1] <-Start again
<- end of loop, check global max length, output
这是 O(n),因为每个指针(L 和 R)仅在任何给定索引上移动一次。
我认为这应该足以让您用您选择的任何语言编写算法。注意循环结束条件,因为如果数组用完,您必须检查全局最大长度。
关于arrays - 算法 - 最小大于大小,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35370432/