我在Reddit上看到了这个问题，但没有给出积极的解决方案，所以我认为这是一个在这里提问的完美问题。这是关于面试问题的一个主题：
编写一个方法，它接受大小为m的int数组，并返回（True/False）如果该数组由n...n+m-1的数字组成，且该范围内仅包含这些数字。不能保证数组已排序。（例如，{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) 否则，从 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]
长度为m的整数数组恰好包含n到n+m-1的所有数字，当且仅当：
（原因：给定整数范围中只有m个值，所以如果数组包含这个范围内的m个唯一值，它必须恰好包含每一个值一次）
如果允许修改数组，则可以使用hazzen算法的修改版本通过一次遍历列表同时检查这两个条件（无需进行任何求和操作）：
我不确定原始数组的修改是否会增加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)。
如果有重复项，我们将在尝试向列表后退交换数字时立即注意到它。
如果我错了，请投票否决我，但我认为我们可以使用方差来确定是否存在重复项。因为我们事先知道平均值（n + (m-1)/2或类似的值），我们只需将数字相加并将其与平均值的差的平方相加，以查看总和是否与方程式（mn + m(m-1)/2）匹配，而方差为（0 + 1 + 4 + ... + (m-1)^2）/m。如果方差不匹配，则很可能存在重复项。
编辑：方差应为（0 + 1 + 4 + ... + [(m-1)/2]^2）*2/m，因为一半的元素小于平均值，另一半大于平均值。
如果存在重复项，则上述方程中的一个术语将与正确的序列不同，即使另一个重复项完全抵消了平均值的变化。因此，该函数仅在总和和方差都与预期值匹配时返回true，我们可以事先计算这些值。
#include<stdio.h>
#define swapxor(a,i,j) a[i]^=a[j];a[j]^=a[i];a[i]^=a[j];
int check_ntom(int a[], int n, int m) {
int i = 0, j = 0;
for(i = 0; i < m; i++) {
if(a[i] < n || a[i] >= n+m) return 0; //invalid entry
j = a[i] - n;
while(j != i) {
if(a[i]==a[j]) return -1; //bucket already occupied. Dupe.
swapxor(a, i, j); //faster bitwise swap
j = a[i] - n;
if(a[i]>=n+m) return 0; //[NEW] invalid entry
}
}
return 200; //OK
}
int main() {
int n=5, m=5;
int a[] = {6, 5, 7, 9, 8};
int r = check_ntom(a, n, m);
printf("%d", r);
return 0;
}
编辑：代码已更改以消除非法内存访问。
for i = 0 to m
if (a[a[i]]==a[i]) return false; // we have a duplicate
while (a[a[i]] > a[i]) swapArrayIndexes(a[i], i)
sum = sum + a[i]
next
if sum = (n+m-1)*m return true else return false
这不是O(n) - 可能更接近于O(n Log n) - 但它确实提供了恒定的空间，并且可能为问题提供了不同的攻击向量。
如果我们想要O(n)，那么使用字节数组和一些位操作将使用额外的n/32字节的内存进行重复检查（当然假设是32位整数）。
编辑：上述算法可以通过将求和检查添加到循环内部并检查以下内容来进一步改进：
if sum > (n+m-1)*m return false
这样它会快速失败。
max-min == m-1 就足够了。 - jfs这是使用Hazzen建议的伪代码加上我的一些想法。它适用于负数，并且不需要任何平方和之类的东西。
function testArray($nums, $n, $m) {
// check the sum. PHP offers this array_sum() method, but it's
// trivial to write your own. O(n) here.
if (array_sum($nums) != ($m * ($m + 2 * $n - 1) / 2)) {
return false; // checksum failed.
}
for ($i = 0; $i < $m; ++$i) {
// check if the number is in the proper range
if ($nums[$i] < $n || $nums[$i] >= $n + $m) {
return false; // value out of range.
}
while (($shouldBe = $nums[$i] - $n) != $i) {
if ($nums[$shouldBe] == $nums[$i]) {
return false; // duplicate
}
$temp = $nums[$i];
$nums[$i] = $nums[$shouldBe];
$nums[$shouldBe] = $temp;
}
}
return true; // huzzah!
}
var_dump(testArray(array(1, 2, 3, 4, 5), 1, 5)); // true
var_dump(testArray(array(5, 4, 3, 2, 1), 1, 5)); // true
var_dump(testArray(array(6, 4, 3, 2, 0), 1, 5)); // false - out of range
var_dump(testArray(array(5, 5, 3, 2, 1), 1, 5)); // false - checksum fail
var_dump(testArray(array(5, 4, 3, 2, 5), 1, 5)); // false - dupe
var_dump(testArray(array(-2, -1, 0, 1, 2), -2, 5)); // true
假设您只知道数组的长度并且允许修改数组，则可以在O（1）空间和O（n）时间内完成。
该过程有两个简单的步骤。 1. 对数组进行“模数排序”。[5,3,2,4] => [4,5,2,3]（O（2n）） 2. 检查每个值的相邻值是否比自身高一（模数）（O（n））
总共需要最多通过数组3次。
模数排序是“棘手”的部分，但目标很简单。将数组中的每个值取出并存储在其自己的地址（模长）上。这需要通过数组进行一次遍历，循环遍历每个位置，通过交换将其值移动到正确的位置，并将目标位置的值移入。如果您移入与刚刚驱逐的值同余的值，则具有重复项并且可以提前退出。 最坏情况下，它是O（2n）。
检查是通过对数组进行单次遍历来检查每个值及其下一个最高邻居的。始终为O（n）。
组合算法为O（n）+ O（2n）= O（3n）= O（n）
我的解决方案的伪代码：
foreach(values[])
while(values[i] 不等于 i)
to-be-evicted = values[i]
evict(values[i]) // 交换到其“正确”的位置
if(values[i]%length == to-be-evicted%length)
return false; // 当我们驱逐该数字时，出现了“重复”
end while
end foreach
foreach(values[])
if((values[i]+1)%length != values[i+1]%length)
return false
end foreach
我在下面包含了Java代码概念证明，它不太美观，但它通过了我为它制作的所有单元测试。 我称这些为'StraightArray'，因为它们对应于顺子（忽略花色的连续序列）的扑克牌手。
public class StraightArray {
static int evict(int[] a, int i) {
int t = a[i];
a[i] = a[t%a.length];
a[t%a.length] = t;
return t;
}
static boolean isStraight(int[] values) {
for(int i = 0; i < values.length; i++) {
while(values[i]%values.length != i) {
int evicted = evict(values, i);
if(evicted%values.length == values[i]%values.length) {
return false;
}
}
}
for(int i = 0; i < values.length-1; i++) {
int n = (values[i]%values.length)+1;
int m = values[(i+1)]%values.length;
if(n != m) {
return false;
}
}
return true;
}
}
k放置在位置(k-minval)，并像您原始的解决方案一样检查冲突。如果满足条件，您将得到一个排序后的数组。 - Rafał Dowgirdboolean determineContinuousArray(int *arr, int len)
{
// Suppose the array is like below:
//int arr[10] = {7,11,14,9,8,100,12,5,13,6};
//int len = sizeof(arr)/sizeof(int);
int n = arr[0];
int *result = new int[len];
for(int i=0; i< len; i++)
result[i] = -1;
for (int i=0; i < len; i++)
{
int cur = arr[i];
int hold ;
if ( arr[i] < n){
n = arr[i];
}
while(true){
if ( cur - n >= len){
cout << "array index out of range: meaning this is not a valid array" << endl;
return false;
}
else if ( result[cur - n] != cur){
hold = result[cur - n];
result[cur - n] = cur;
if (hold == -1) break;
cur = hold;
}else{
cout << "found duplicate number " << cur << endl;
return false;
}
}
}
cout << "this is a valid array" << endl;
for(int j=0 ; j< len; j++)
cout << result[j] << "," ;
cout << endl;
return true;
}
n是否为该问题的输入参数。 - AnT stands with Russia