最近有一个面试问题要求我在尽可能短的计算时间内找到重复数值的最大子数组，给定一个已排序的数组。
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不是我的强项。）我的第二个问题只是出于好奇，是否有更高效的算法？
对于这个问题，最好的解决方案是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） 。O(n)。 - verdesmaraldO(n)。在最坏的情况下，maxLength 是 1，而 i += maxLength 只是变成了 i += 1。 - verdesmaraldn 个元素被访问，每个被访问的元素都有一个恒定数量的计算，因此运行时间为 O(n)。A[1..n]：max_start = max_end = 1
max_length = 1
start = end = 1
while start < n
while A[start] == A[end] && end < n
end++
if end - start > max_length
max_start = start
max_end = end - 1
max_length = end - start
start = end
end = start + max_length 开始而不是 end = start + 1。虽然时间复杂度仍为 O(n)，但大多数情况下速度更快。 - verdesmarald我认为我们都同意，在最坏的情况下，即所有A都是唯一的或所有A都相同的情况下，您必须检查数组中的每个元素，以确定是否存在重复项或确定数组包含一个数字。就像其他帖子中所说的那样，这将是O(N)。我不确定分治法在算法复杂度上能够帮助您很多，尽管您可能可以通过使用递归来简化代码。当您可以丢弃大量输入时（例如二分搜索），分治法确实有助于减少大O，但在您可能需要检查所有输入的情况下，它并没有什么不同。
我假设这里的结果只是返回您找到的最大B的大小，尽管您可以轻松修改此结果以返回B。
关于算法，考虑到A已经排序，我不确定是否有比按顺序遍历数组更快/更简单的答案。最简单的方法似乎是使用两个指针，一个从索引0开始，另一个从索引1开始。比较它们，然后将它们都增加；每次它们相同时，您将计数器向上移动以给出当前B的大小，并且当它们不同时，您将该计数器重置为零。您还需要保留一个变量来存储迄今为止找到的最大B的大小，并在找到更大的B时更新它。
假设最长连续整数只有长度为1，那么您将扫描整个n项数组A。因此，复杂度不是以n为单位，而是以len(B)为单位。
不确定复杂度是否为O(n/len(B))。
检查2个边缘情况
- 当n == len(B)时，您会得到即时结果（仅检查A [0]和A [n-1]
- 当n == 1时，您会得到O(n)，检查所有元素
- 在正常情况下，我太懒了，不想编写算法进行分析...
编辑
考虑到len(B)事先未知，我们必须采取最坏情况，即O(n)