给定一个排序数组，找到重复值的最大子数组

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

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不是我的特长）而我的第二个问题纯粹是因为我的好奇心，是否有更省时的算法？

来源

2012-09-15 user1246462

我挺你的问题混淆。你能详细描述面试官的意思吗？（什么是“紧张”？）你能否更详细地描述你的解决方案？（可能使用伪代码。） – svick

未提供更多详细信息。我基本上用分而治之。 – user1246462

请修改您的标题，以便将来对本网站的用户更有用。 –

对于这个问题你可以做的最好的解决方案是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）

来源

2012-09-15 14:07:50 verdesmarald

应该有一个比O（n）更紧的界限.OP的算法听起来比扫描阵列效率更高从第一次开始o最后一个元素 –

我们在这里讨论最坏的情况。在最坏的情况下（即每个元素都是唯一的），你必须检查每个元素='O（n）'。 – verdesmarald

你忘了说你的解决方案的时间复杂度是多少。 – svick

-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-15 14:06:39

这个答案是不正确的，计算复杂度类别的方式是相对于输入元素的数量，并且默认情况下是指算法的最坏情况运行时间，即除非另有说明。如果不是，我可以说我的（强力）算法的运行时间会破坏符合标准的AES加密，因为它可能会非常幸运并首先测试正确的密钥... – lol

Downvoted试图界定更紧密的界限？ :( 该OP的算法肯定比线性搜索更好，并且肯定对len（B） –

@ lol有依赖关系，如果AES加密存在缺陷并且倾向于以连续方式重用密钥，利用这种模式，你的算法仍然是O（n）吗？或者它取决于有多少个连续的重用密钥？ –

我想我们大家都同意，在最坏的情况下，所有的A都是独一无二的，或者全部是A是相同的，你必须检查数组中的每个元素，以确定没有重复或确定所有数组包含一个数字。就像其他海报所说的那样，那将是O(N)。我不确定分裂&征服可以帮助你解决这个问题的算法复杂性，尽管你可以通过递归来简化代码。除以&当你可以丢掉大部分输入（例如二进制搜索）时，conquer确实有助于减少Big O，但是在你可能必须检查所有输入的情况下，它不会有太大的不同。

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

所以在算法方面，考虑到A是排序的，我不确定会有什么答案比只按顺序遍历数组更快/更简单。看起来最简单的答案是有两个指针，一个指针从索引0开始，另一个从索引1开始。比较它们，然后对它们进行增加;每次它们相同时，您向上勾选一个计数器以给出当前尺寸B，当它们不同时，将该计数器重置为零。您还保留了迄今为止发现的B的最大大小的变量，并在每次找到更大的B时更新它。

来源

2012-09-15 14:38:40

同意，最坏的情况，“所有独特的”，成本O（N）。但是“全部相同”可以立即从A [1] == A [n];这是O（1），我会称这是最好的情况。 – Quigi

在这个算法中，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-15 14:42:03

你最好从'end = start + max_length'开始，而不是'end = start + 1'。它仍然是'O（n）'，但大部分时间都更快。 – verdesmarald

你说得对。这个特定算法的要点是简单性，以便更容易看出数组中的每个元素如何执行额外的操作。 –

给定一个排序数组，找到重复值的最大子数组

回答

相关问题