在线性时间内删除数组中的重复项并且不需要额外的数组

Question

我们有一个数组，它是未排序的。我们知道范围是[0，n]。

我们要删除重复，但我们不能使用额外的数组而且必须运行线性时间。

任何想法？只是为了澄清，这不是作业！

Answer 1

如果整数限制为0到n，则可以在数组中移动，将数字按其索引进行排列。每次您替换一个号码时，都要将原来的值移到该位置。举例来说，假设我们有大小8的数组：

----------------- 
|3|6|3|4|5|1|7|7| 
----------------- 
S 

其中S是我们的起点，我们将用C来跟踪我们的“当前”的指标。 我们从索引0开始，将3移动到3索引点，其中4是。保存4个临时变量。

----------------- 
|X|6|3|3|5|1|7|7| Saved 4 
----------------- 
S  C 

我们再放入4索引4，节省了曾经被认为是有，5

----------------- 
|X|6|3|3|4|1|7|7| Saved 5 
----------------- 
S  C 

继续下去

----------------- 
|X|6|3|3|4|5|7|7| Saved 1 
----------------- 
S   C 

----------------- 
|X|1|3|3|4|5|7|7| Saved 6 
----------------- 
S C 

----------------- 
|X|1|3|3|4|5|6|7| Saved 7  
----------------- 
S   C 

当我们尝试更换7，我们可以看到冲突，所以我们根本就不放。然后，我们从起点性索引继续，加1是：

----------------- 
|X|1|3|3|4|5|6|7| 
----------------- 
    S   

1是在这里很好，3只需要移动

----------------- 
|X|1|X|3|4|5|6|7| 
----------------- 
    S 

但3是重复的，所以我们把它扔掉，并保持遍历数组的其余部分。

所以基本上，我们最多移动一个条目1次，并遍历整个数组。那是O（2n）= O（n）

Answer 2

你能排序吗？用基数排序 - http://en.wikipedia.org/wiki/Radix_sort复杂度为O（arraySize）给定的情况下，然后从排序的数组O（arraySize）中删除重复。

Answer 3

假设int a[n]是范围[0，n-1]中的一个整数数组。请注意，这与所陈述的问题略有不同，但我做了这个假设以明确算法的工作原理。该算法可以修补为[0，n]范围内的整数。

for (int i=0; i<n; i++) 
{ 
    if (a[i] != i) 
    { 
     j = a[i]; 
     k = a[j]; 
     a[j] = j; // Swap a[j] and a[i] 
     a[i] = k; 
    } 
} 

for (int i=0; i<n; i++) 
{ 
    if (a[i] == i) 
    { 
     printf("%d\n", i); 
    } 
} 

Answer 4

void printRepeating(int arr[], int size) 
{ 
    int i; 
    printf("The repeating elements are: \n"); 
    for(i = 0; i < size; i++) 
    { 
    if(arr[abs(arr[i])] >= 0) 
     arr[abs(arr[i])] = -arr[abs(arr[i])]; 
    else 
     printf(" %d ", abs(arr[i])); 
    } 
} 

Answer 5

走过数组指派阵列[阵列[I] = -array [阵列[I]];如果不是负面的;如果它已经是负的那么它的重复，这将工作，因为所有的值都在0和n之内。

Answer 6

扩展@Joel Lee的代码以完成。

#include <iostream> 
void remove_duplicates(int *a, int size) 
{ 
    int i, j, k; 
    bool swap = true; 

    while(swap){ 
    swap = false; 
    for (i=0; i<size; i++){ 
     if(a[i] != i && a[i] != a[a[i]]){ 
      j = a[i]; 
      k = a[j]; 
      a[i] = k; 
      a[j] = j; 
      swap = true;  
     } 

    } 
    } 
} 

int main() 
{ 
    int i; 
    //int array[8] = {3,6,3,4,5,1,7,7}; 
    int array[8] = {7,4,6,3,5,4,6,2}; 

    remove_duplicates(array, sizeof(array)/sizeof(int)); 

    for (int i=0; i<8; i++) 
     if(array[i] == i) 
      std::cout << array[i] << " "; 

    return 0; 
}