在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它指向的位置是否是本地位置发现它不是。 在这种情况下,我们不知道mA[m]是否是重复的值,但是我们知道,无论哪种方式, 都已经被报告 ,因为这两个循环被保证不出现在caf第一循环的结果中。 (注意,如果m != A[m]那么mA[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 ++,但无论如何

http://ideone.com/GRZPI

不是很漂亮,但至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)。