假设不允许使用小于一的数字且不存在重复元素,则对于这个问题有一个简单的求和公式 - 从 1
到 m
,以 1
递增,所有数字的和等于 (m * (m + 1)) / 2
。接着可以将数组相加并使用这个公式。
在上述保证条件下,可以确定是否存在重复项,加上保证没有数字大于 m 或小于 n (可以在 O(N)
时间内检查)。
伪代码如下:
0) 从 N = 0 开始
1) 取出列表中第 N 个元素
2) 如果它没有按排序后的顺序排列,找出它在哪个位置上应该排列
3) 如果应该排列的位置已经有同样的数字,那么就有重复项 - 返回 TRUE
4) 否则,交换这两个数字(把第一个数字放到正确的位置上)
5) 对于你刚才交换的数字,它是否处于正确的位置上?
6) 如果不是,返回步骤二
7) 否则,从 N = N + 1 开始执行第一步。如果这会超出列表的末尾,则没有重复项。
是的,这个方法的时间复杂度为 O(N)
,尽管它看起来像O(N ^ 2)
。
注(总结自评论)
此解决方案假定可以修改数组,然后使用原地基数排序(实现了 O(N)
的速度)。
其他数学解法也被提出,但我不确定它们是否已被证明。有许多求和公式可能有用,但大部分都会遇到表示总和所需位数激增的问题,这将违反额外空间保证的常量限制。我也不知道其中哪些能够为给定数字集合产生不同的数字。我认为平方和可能有效,因为有一个已知的计算公式(参见Wolfram's)
新的见解(嗯,更多的是我正在思考,虽然不能帮助解决问题,但很有趣,我要睡觉了):
所以,有人提到可以使用总和+平方和。没有人知道这是否有效,我意识到只有当(x+y)=(n+m)时才会成为问题,例如事实上2 + 2 = 1 + 3。由于毕达哥拉斯三元数,平方也存在这个问题(所以3 ^ 2 + 4 ^ 2 + 25 ^ 2 == 5 ^ 2 + 7 ^ 2 + 24 ^ 2,平方和不起作用)。如果我们使用费马大定理,我们知道这在n³中不会发生。但是,我们也不知道是否对于这个问题没有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的所有数字,当且仅当:
- 每个数组元素都在n和n+m-1之间
- 没有重复的数字
(原因:给定整数范围中只有m个值,所以如果数组包含这个范围内的m个唯一值,它必须恰好包含每一个值一次)
如果允许修改数组,则可以使用hazzen算法的修改版本通过一次遍历列表同时检查这两个条件(无需进行任何求和操作):
- 对于所有从0到m-1的数组索引i执行以下操作
- 如果array[i] < n或array[i] >= n+m => 返回FALSE(“找到超出范围的值”)
- 计算j = array[i] - n (这是一个值从n到n+m-1排序后的数组中array[i]的基于0的位置)
- 当j不等于i时
- 如果list[i]等于list[j] => 返回FALSE(“找到重复值”)
- 交换list[i]和list[j]
- 重新计算j = array[i] - n
- 返回TRUE
我不确定原始数组的修改是否会增加O(1)的最大额外空间,但如果不会,这应该是原作者想要的解决方案。
n
是否为该问题的输入参数。 - AnT stands with Russia