另一个面试问题要求我在尽可能短的计算时间内找到给定排序数组的重复值的最大可能子数组。
Let input array be A[1 ... n]
Find an array B of consecutive integers in A such that:
for x in range(len(B)-1):
B[x] == B[x+1]
我认为最好的算法是将数组分成两半，从中间向外，从中间开始比较整数，然后从中间找到相同整数的最长应变。然后我会通过将数组分成两半并在两半上调用方法来递归调用该方法。
我的面试官说我的算法很好，但我对算法是 O(logn) 的分析是不正确的，但从来没有抽出时间告诉我正确答案是什么。我的第一个问题是这个算法的 Big-O 分析是什么？ (请展示尽可能多的工作!Big-O 不是我的强项。)我的第二个问题纯粹是出于好奇，是否有更省时的算法？
最佳答案
你能为这个问题做的最好的事情是O(n) 解决方案，所以你的算法不可能既正确又O(lg n)。
例如，考虑数组不包含重复元素的情况。要确定这一点，需要检查每个元素，检查每个元素是 O(n)。
这是一个简单的算法，可以找到重复元素的最长子序列:
start = end = 0
maxLength = 0
i = 0
while i + maxLength < a.length:
if a[i] == a[i + maxLength]:
while i + maxLength < a.length and a[i] == a[i + maxLength]:
maxLength += 1
start = i
end = i + maxLength
i += maxLength
return a[start:end]
如果您有理由相信子序列会很长，您可以将 maxLength 的初始值设置为一些启发式选择的值以加快速度，然后仅在您不这样做时寻找较短的序列找不到一个(即你在第一次通过后以 end == 0 结束。)
关于algorithm - 给定一个排序数组，找到重复值的最大子数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12437887/