在O（n）时间和O（1）空间中查找重复项
input：给定包含从0到n-1的元素的n个元素的数组，其中任何这些数字出现任何次数。
目标：在O（n）中find这些重复的数字，并只使用恒定的内存空间。
例如，令n为7，数组为{1,2,3,1,3,0,6}，答案应该是1＆3.我在这里查了类似的问题，但答案使用了一些数据结构，如HashSet等
任何有效的algorithm相同？
这是我想出来的，不需要额外的符号位：
for i := 0 to n - 1 while A[A[i]] != A[i] swap(A[i], A[A[i]]) end while end for for i := 0 to n - 1 if A[i] != i then print A[i] end if end for
第一个循环对数组进行置换，以便如果元素x至less存在一次，那么其中一个将位于A[x]位置。
请注意，它可能不会在第一时间看O（n），但它是 – 虽然它有一个嵌套循环，它仍然运行在O(N)时间。 一个交换只发生，如果有一个i这样的A[i] != i ，每个交换至less设置一个元素，使得A[i] == i ，如果以前不是这样的话。 这意味着交换的总次数（以及因此while循环体的总执行次数）最多为N-1 。
第二个循环打印x的值不等于x – 因为第一个循环保证如果x在数组中至less存在一次，那么其中一个实例将在A[x] ，这意味着它会打印出数组中不存在的那些x值。
（Ideone链接，所以你可以玩它）
caf的辉煌答案将k-1次出现k次的每个数字打印出来。 这是有用的行为，但是这个问题可以说是要求每个副本只打印一次，他暗示了这样做的可能性，而不是吹出线性时间/恒定的空间范围。 这可以通过用以下伪代码replace他的第二个循环来完成：
for (i = 0; i < N; ++i) { if (A[i] != i && A[A[i]] == A[i]) { print A[i]; A[A[i]] = i; } }
这利用了第一个循环运行后的属性，如果任何值m出现多次，那么这些外观中的一个保证处于正确的位置，即A[m] 。 如果我们非常小心的话，我们可以使用这个“家”位置来存储是否有任何重复的信息。
在caf的版本中，当我们通过数组时， A[i] != i意味着A[i]是重复的。 在我的版本中，我依赖于一个稍微不同的不变式： A[i] != i && A[A[i]] == A[i]意味着A[i]是我们以前没有见过的重复。 （如果你放弃了“我们以前没有见过的东西”的部分，其余部分可以被看作是caf不变的真实性的保证，并且保证所有重复的东西在家中都有一些副本）。一开始（咖啡馆的第一个循环完成后），我下面显示，它是在每一步后保持。
当我们通过这个数组的时候，在A[i] != i部分的testing中的成功意味着A[i] 可能是以前没有见过的重复。 如果我们之前没有看到过，那么我们预计A[i]的家位置指向自己 – 这是在if条件的后半部分testing的。 如果是这种情况，我们打印它，并改变家庭位置指向这个第一次发现的重复，创build一个两步“循环”。
为了看到这个操作不改变我们的不variables，假设对于满足A[i] != i && A[A[i]] == A[i] m = A[i]的特定位置， m = A[i] A[i] != i && A[A[i]] == A[i] 。 很明显，我们所做的改变（ A[A[i]] = i ）将会阻止其他非家庭事件m被输出为重复，通过导致他们的if条件的后半部分失败，当i到达家中的位置时， 是的，因为现在，即使在这个新的i我们发现if条件的前半部分A[i] != i是真的，那么下半部分将testing它指向的位置是否是本地位置发现它不是。 在这种情况下，我们不知道m或A[m]是否是重复的值，但是我们知道，无论哪种方式， 都已经被报告 ，因为这两个循环被保证不出现在caf第一循环的结果中。 （注意，如果m != A[m]那么m和A[m]只有一个出现，而另一个则根本不出现。
这是伪代码
for i <- 0 to n-1: if (A[abs(A[i])]) >= 0 : (A[abs(A[i])]) = -(A[abs(A[i])]) else print i end for
在C ++中的示例代码
对于相对较小的N，我们可以使用div / mod操作
n.times do |i| e = a[i]%n a[e] += n end n.times do |i| count = a[i]/n puts i if count > 1 end
不是C / C ++，但无论如何
不是很漂亮，但至less很容易看到O（N）和O（1）属性。 基本上我们扫描数组，并且对于每个数字，我们看到相应的位置是否已经被标记为已经看过一次（N）或已经看过多次（N + 1）。 如果它已经被标记了一次，我们会打印它并且多次标记它已经被看到。 如果没有标记，我们将其标记为已经看过一次，并将相应索引的原始值移动到当前位置（标记是一个破坏性操作）。
for (i=0; i<a.length; i++) { value = a[i]; if (value >= N) continue; if (a[value] == N) { a[value] = N+1; print value; } else if (a[value] < N) { if (value > i) a[i--] = a[value]; a[value] = N; } }
或者，更好（尽pipe双循环，更快）：
for (i=0; i<a.length; i++) { value = a[i]; while (value < N) { if (a[value] == N) { a[value] = N+1; print value; value = N; } else if (a[value] < N) { newvalue = value > i ? a[value] : N; a[value] = N; value = newvalue; } } }
C中的一个解决scheme是：
#include <stdio.h> int finddup(int *arr,int len) { int i; printf("Duplicate Elements ::"); for(i = 0; i < len; i++) { if(arr[abs(arr[i])] > 0) arr[abs(arr[i])] = -arr[abs(arr[i])]; else if(arr[abs(arr[i])] == 0) { arr[abs(arr[i])] = - len ; } else printf("%d ", abs(arr[i])); } } int main() { int arr1[]={0,1,1,2,2,0,2,0,0,5}; finddup(arr1,sizeof(arr1)/sizeof(arr1[0])); return 0; }
O（n）时间和O（1）空间复杂度。
一个小的python代码来演示上面的caf的方法：
a = [3, 1, 1, 0, 4, 4, 6] n = len(a) for i in range(0,n): if a[ a[i] ] != a[i]: a[a[i]], a[i] = a[i], a[a[i]] for i in range(0,n): if a[i] != i: print( a[i] )
在下面的C函数中可以很容易地看到algorithm。 检索原始数组，虽然不是必需的，但是可以以每个模n为模入口。
void print_repeats(unsigned a[], unsigned n) { unsigned i, _2n = 2*n; for(i = 0; i < n; ++i) if(a[a[i] % n] < _2n) a[a[i] % n] += n; for(i = 0; i < n; ++i) if(a[i] >= _2n) printf("%u ", i); putchar('\n'); }
Ideone Link进行testing。
static void findrepeat() { int[] arr = new int[7] {0,2,1,0,0,4,4}; for (int i = 0; i < arr.Length; i++) { if (i != arr[i]) { if (arr[i] == arr[arr[i]]) { Console.WriteLine(arr[i] + "!!!"); } int t = arr[i]; arr[i] = arr[arr[i]]; arr[t] = t; } } for (int j = 0; j < arr.Length; j++) { Console.Write(arr[j] + " "); } Console.WriteLine(); for (int j = 0; j < arr.Length; j++) { if (j == arr[j]) { arr[j] = 1; } else { arr[arr[j]]++; arr[j] = 0; } } for (int j = 0; j < arr.Length; j++) { Console.Write(arr[j] + " "); } Console.WriteLine(); }
假设我们将这个数组作为一个单向图数据结构 – 每个数字都是一个顶点，并且它的数组中的索引指向形成图的一个边的另一个顶点。
为了更简单，我们有索引0到n-1，数字范围从0..n-1。 例如
0 1 2 3 4 a[3, 2, 4, 3, 1]
0（3）→3（3）是一个循环。
答案只需要依靠索引遍历数组。 如果a [x] = a [y]那么它是一个循环，因此是重复的。 跳到下一个索引，然后再继续，直到数组结束。 复杂性：O（n）时间和O（1）空间。
如果数组不是太大这个解决scheme更简单，它会创build另一个相同大小的数组作为滴答。
1创build一个与您的input数组大小相同的位图/数组
int check_list[SIZE_OF_INPUT]; for(n elements in checklist) check_list[i]=0; //initialize to zero
2扫描你的input数组，并在上面的数组中增加它的计数
for(i=0;i<n;i++) // every element in input array { check_list[a[i]]++; //increment its count }
3现在扫描check_list数组并打印重复一次或多次重复
for(i=0;i<n;i++) { if(check_list[i]>1) // appeared as duplicate { printf(" ",i); } }
当然，上面给出的解决scheme消耗的空间是两倍，但是时间效率是O（2n），基本上是O（n）。
