4

还有一个面试问题要求我在可能的最短计算时间内找到给定排序数组的最大可能重复值子数组。

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 不是我的强项。）我的第二个问题纯粹是出于好奇，是否有更省时的算法？

4

4 回答 4

4

对于这个问题，你能做的最好的就是一个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 == 0after第一关。）

于 2012-09-15T14:07:50.517 回答
0

我想我们都同意，在最坏的情况下，所有的A都是唯一的或所有的A都是相同的，您必须检查数组中的每个元素以确定没有重复项或确定所有数组都包含一个数字。就像其他海报所说的那样，那将是O(N)。我不确定分治法在这方面对您的算法复杂性有多大帮助，尽管您可以通过使用递归来稍微简化代码。当您可以丢弃大部分输入（例如二进制搜索）时，分而治之确实有助于减少 Big O，但在您可能必须检查所有输入的情况下，它不会有太大不同。

我假设这里的结果是你只是返回你找到的最大 B 的大小，尽管你可以很容易地修改它来返回 B 。

因此，在算法方面，鉴于 A 已排序，我不确定是否会有比按顺序遍历数组更快/更简单的答案。似乎最简单的答案是有 2 个指针，一个从索引 0 开始，一个从索引 1 开始。比较它们，然后将它们都递增；每次它们相同时，您向上勾选一个计数器以提供当前大小，B当它们不同时，您将该计数器重置为零。您还为迄今为止找到的 B 的最大大小保留一个变量，并在每次找到更大的B.

于 2012-09-15T14:38:40.420 回答
0

在这个算法中，n元素被访问，每个被访问元素的计算次数是恒定的，所以运行时间是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
于 2012-09-15T14:42:03.110 回答
-1

假设最长连续整数的长度仅为 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)

于 2012-09-15T14:06:39.433 回答