确定数组是否包含n ... n + m的算法？

我在Reddit上看到了这个问题,并没有提出积极的解决方案,我认为这是一个完美的问题.这是关于面试问题的一个主题:

编写一个采用大小为m的int数组的方法,如果数组由数字n ... n + m-1组成,则返回(True/False),该范围内的所有数字以及该范围内的数字.不保证数组已排序.(例如,{2,3,4}将返回true.{1,3,1}将返回false,{1,2,4}将返回false.

我遇到的问题是我的采访者一直要求我优化(更快的O(n),更少的内存等),他声称你可以在数组的一次传递中使用恒定量的记忆.从未想过那一个.

除了您的解决方案,请指出他们是否认为该阵列包含唯一的项目.同时指出您的解决方案是否假设序列从1开始.(我稍微修改了一下这个问题以允许它变为2,3,4 ......)

编辑:我现在认为在空间算法中不存在处理重复的线性时间和常数.任何人都可以验证吗？

重复问题归结为测试以查看数组是否在O(n)时间,O(1)空间中包含重复项.如果可以这样做,您可以先测试,如果没有重复,则运行算法.那么你可以在O(n)时间O(1)空间中测试欺骗吗？

在此假设下数少于一个是不允许的,并没有重复,有一个这样的简单相加的身份-数字从和1到m增量为1是(m * (m + 1)) / 2.然后,您可以对数组求和并使用此标识.

您可以查看是否有上述保证下的欺骗,加上保证没有数字大于m或小于n(可以登记O(N))

伪代码中的想法:
0)从N = 0开始
1)取列表中的第N个元素.
2)如果列表已经排序,如果它不在正确的位置,请检查它应该在哪里.
3)如果它应该已经具有相同数字的地方,你有一个欺骗 - 返回TRUE
4)否则,交换数字(将第一个数字放在正确的位置).
5)使用您刚刚交换的号码,它是否在正确的位置？
6)如果不是,请返回第二步.
7)否则,从步骤1开始,N = N + 1.如果这将超过列表的末尾,则表示没有欺骗.

并且,是的,O(N)虽然它可能看起来像是在运行O(N ^ 2)

每个人都注意(从评论中收集的东西)

此解决方案可以在您可以修改数组的假设下工作,然后使用就地Radix排序(实现O(N)速度).

已经提出了其他的解决方案,但我不确定它们中是否有任何证据.有一堆可能有用的总和,但是大多数会遇到表示总和所需的位数的爆炸,这将违反恒定的额外空间保证.我也不知道他们中的任何一个是否能够为给定的一组数字产生一个不同的数字.我认为一个正方形可能有效,它有一个已知的公式来计算它(参见Wolfram的)

新的见解(好吧,更多的思考无助于解决它,但很有趣,我要去睡觉):

因此,已经提到可以使用和+平方和.没有人知道这是否有效,并且我意识到当(x + y)=(n + m)时它只会成为一个问题,例如事实2 + 2 = 1 + 3. Squares也有这个问题归功于毕达哥拉斯三重奏(所以3 ^ 2 + 4 ^ 2 + 25 ^ 2 == 5 ^ 2 + 7 ^ 2 + 24 ^ 2,并且平方和不起作用).如果我们使用费马的最后定理,我们知道n ^ 3不会发生这种情况.但我们也不知道是否没有x + y + z = n(除非我们这样做而且我不知道).所以不能保证这一点也不会破坏 - 如果我们继续沿着这条路走下去,我们就会很快耗尽.

然而,在我的欢乐中,我忘记了你可以打破正方形的总和,但这样做你创建一个无效的正常总和.我不认为你可以做到这两点,但是,正如已经指出的那样,我们没有任何证据.

我必须说,找到反例有时比证明事情要容易得多!考虑以下序列,所有序列的总和为28,平方和为140:

[1, 2, 3, 4, 5, 6, 7]
[1, 1, 4, 5, 5, 6, 6] 
[2, 2, 3, 3, 4, 7, 7]

我找不到任何长度为6或更短的例子.如果您想要一个具有正确的最小值和最大值的示例,请尝试以下长度为8的示例:

[1, 3, 3, 4, 4, 5, 8, 8]

更简单的方法(修改hazzen的想法):

长度为m的整数数组包含从n到n + m-1的所有数字,恰好是iff

每个数组元素都在n和n + m-1之间

没有重复

(原因:在给定的整数范围内只有m个值,因此如果数组在此范围内包含m个唯一值,则它必须包含每个值一次)

如果允许修改数组,则可以使用hazzen算法构思的修改版本在列表中一次检查两者(不需要进行任何求和):

对于从0到m-1的所有数组索引

如果array [i] = n + m => RETURN FALSE("值超出范围")

计算j = array [i] - n(这是排序数组中数组[i]的从0开始的位置,其值从n到n + m-1)

虽然j不等于i

如果list [i]等于list [j] => RETURN FALSE("找到重复")

用列表[j]交换列表[i]

重新计算j = array [i] - n

返回

我不确定原始数组的修改是否计入O(1)的最大允许额外空间,但如果没有,这应该是原始海报想要的解决方案.

通过与您合作a[i] % a.length而不是a[i]将问题减少到需要确定您已获得数字0的问题a.length - 1.

我们认为这个观察是理所当然的,并尝试检查数组是否包含[0,m).

找到不在其正确位置的第一个节点,例如

0 1 2 3 7 5 6 8 4 ;     the original dataset (after the renaming we discussed)
        ^
        `---this is position 4 and the 7 shouldn't be here

将该数字交换到应该的位置.即交换7用8:

0 1 2 3 8 5 6 7 4 ; 
        |     `--------- 7 is in the right place.
        `--------------- this is now the 'current' position

现在我们重复一遍.再看看我们目前的立场,我们会问:

"这是正确的号码吗？"

如果没有,我们将其交换到正确的位置.

如果它在正确的位置,我们向右移动并再次执行此操作.

再次遵循这条规则,我们得到:

0 1 2 3 4 5 6 7 8 ;     4 and 8 were just swapped

这将从左到右正确地逐步建立列表,并且每个数字最多移动一次,因此这是O(n).

如果存在欺骗行为,我们会立即注意到它是否会尝试交换backwards列表中的数字.