数组去重

Question

我有一个未排序的数组，如何最好地删除所有重复的元素？

例如：

a[1,5,2,6,8,9,1,1,10,3,2,4,1,3,11,3]

因此，在进行该操作后，数组应该看起来像

 a[1,5,2,6,8,9,10,3,4,11]

- mohit

---

这是作业吗？如果不是的话，很多语言（至少脚本语言）都内置了这个功能。Ruby：[1, 2, 3, 2, 3, 1].uniq - jtbandes

使用一个临时字典，在读取元素时将其插入，以便在字典中已存在时将其移除。 - pascal

@jtbandes 这不是作业..我只是想知道基本上适当的算法。@pascal 使用临时字典意味着使用额外的内存（存储）吗？ - mohit

是的，例如，请参考马修的回答。 - pascal

如果您是C++用户，则可以在C++ STL <algorithm>中使用unique()函数。 - Abhinav Shrivastava

你可以观看这个链接，了解同样的问题：http://stackoverflow.com/questions/24944844/removing-duplicates-inside-insertion-sort/26177449#26177449 - isxaker

Answer 1

检查每个元素与其他元素是否重复

朴素的解法是对每个元素都与其余元素进行比较。这种方法效率低下，即使你只进行“向前”比较，也会得到O(n²)的复杂度。

排序后去重

更好的方法是对数组进行排序，然后检查每个元素是否与其相邻的元素重复。选择高效的排序算法，复杂度为O(n log n)。

基于排序的方法的缺点是无法保持原有的顺序。但可以通过额外的步骤来解决这个问题。将所有条目（在唯一排序的数组中）放入哈希表中，哈希表具有O(1)访问时间。然后遍历原始数组，对于每个元素，检查它是否在哈希表中。如果在哈希表中，则将其添加到结果数组并从哈希表中删除它。最终得到的结果数组保留了原数组的顺序，每个元素都出现在其第一次出现的位置。

整数线性排序

如果您处理的是一定范围内的整数，可以使用基数排序来提高效率。例如，如果假设这些数字都在0到1,000,000之间，可以分配一个大小为1,000,001的位向量。对于原始数组中的每个元素，根据其值设置相应的位（例如，值为13会导致设置第14位）。然后遍历原始数组，检查它是否在位向量中。如果是，则将其添加到结果数组中并从位向量中清除该位。这个方法是O(n)，以空间换时间。

哈希表解法

最好的解决方法是创建一个O(1)访问的哈希表。遍历原始列表。如果它不在哈希表中，则将它添加到结果数组和哈希表中。如果它已经在哈希表中，就忽略它。

这绝对是最好的解决方案。那为什么还会有其他方法呢？因为像这样的问题在于将你所拥有（或应该拥有）的知识适应到问题中，并基于你所做的假设进行优化，从而得出一个解决方案。进化解决方案并理解其中的思考过程比简单地重复一个解决方案更有用。

此外，散列表并不总是可用的。在嵌入式系统或空间非常有限的场景下，您可以使用少量操作码实现快速排序，比任何散列表需要更少的操作码。

- cletus

---

这个问题中，结果数组似乎保留了输入数组的顺序。 - pascal

应该明确一点，哈希表只能提供预期常数时间，而不能保证常数时间。 - rbrito

虽然哈希表不允许添加重复项，但如果您将哈希表中的所有数字相加，然后简单地打印它，您可以得到相同的结果。使用一些if条件语句会使逻辑更加复杂，那么上述的意义是什么呢？ - Gökhan Akduğan

@GökhanAkduğan 最明显的原因是：排序的重要性、缺乏哈希表可用性和强烈的空间限制。 - Szymon Brych

为什么在哈希表中找到重复项后要将其删除？重复项也可能意味着三元组、四元组等。我不会从哈希表中删除该值。 - Rudy Velthuis

我不知道哈希表是迄今为止最好的，尽管它的理论复杂度是如此。排序非常高效且缓存友好。只需考虑处理哈希表冲突的所有复杂性。 - Justin Meiners

Answer 2

这可以通过使用基于哈希表的集合，在分摊复杂度为O(n)的情况下完成。

伪代码如下：

s := new HashSet
c := 0
for each el in a
  Add el to s.
    If el was not already in s, move (copy) el c positions left.
    If it was in s, increment c. 

- Matthew Flaschen

Answer 3

如果您不需要保留原始对象，可以循环它并创建一个新的唯一值数组。在C#中，使用List来获得所需的功能。这并不是最具吸引力或最智能的解决方案，但它有效。

int[] numbers = new int[] {1,2,3,4,5,1,2,2,2,3,4,5,5,5,5,4,3,2,3,4,5};
List<int> unique = new List<int>();

foreach (int i in numbers)
     if (!unique.Contains(i))
          unique.Add(i);

unique.Sort();
numbers = unique.ToArray();

- William

Answer 4

Treat numbers as keys.

for each elem in array:
if hash(elem) == 1 //duplicate
  ignore it
  next
else
  hash(elem) = 1
  add this to resulting array 
end

If you know about the data like the range of numbers and if it is finite, then you can initialize that big array with ZERO's.

array flag[N] //N is the max number in the array
for each elem in input array:
  if flag[elem - 1] == 0
    flag[elem - 1] = 1
    add it to resulatant array
  else
    discard it //duplicate
  end

- bhups

Answer 5

    indexOutput = 1;
    outputArray[0] = arrayInt[0];
    int j;
    for (int i = 1; i < arrayInt.length; i++) {            
        j = 0;
        while ((outputArray[j] != arrayInt[i]) && j < indexOutput) {
            j++;
        }
        if(j == indexOutput){
           outputArray[indexOutput] = arrayInt[i];
           indexOutput++;
        }         
    }

- dhayyati

Answer 6

你可以在Python中使用“in”和“not in”语法，使其变得非常直观。

不过，与哈希方法相比，复杂度会更高，因为“not in”相当于进行线性遍历，以确定该条目是否存在。

li = map(int, raw_input().split(","))
a = []
for i in li:
    if i not in a:
        a.append(i)
print a

- Deepak Pathania

Answer 7

Time O(n) space O(n) 

#include <iostream>
    #include<limits.h>
    using namespace std;
    void fun(int arr[],int size){

        int count=0;
        int has[100]={0};
        for(int i=0;i<size;i++){
            if(!has[arr[i]]){
               arr[count++]=arr[i];
               has[arr[i]]=1;
            }
        }
     for(int i=0;i<count;i++)
       cout<<arr[i]<<" ";
    }

    int main()
    {
        //cout << "Hello World!" << endl;
        int arr[]={4, 8, 4, 1, 1, 2, 9};
        int size=sizeof(arr)/sizeof(arr[0]);
        fun(arr,size);

        return 0;
    }

- rjnitt

Answer 8

我正在用Python进行。

array1 = [1,2,2,3,3,3,4,5,6,4,4,5,5,5,5,10,10,8,7,7,9,10]

array1.sort() # sorting is must
print(array1)

current = NONE
count = 0 

# overwriting the numbers at the frontal part of the array
for item in array1:
    if item != current:
        array1[count] = item
        count +=1
        current=item
        
       

print(array1)#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 5, 5, 5, 5, 6, 7, 7, 8, 9, 10, 10, 10]

print(array1[:count])#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

最有效的方法是：

array1 = [1,2,2,3,3,3,4,5,6,4,4,5,5,5,5,10,10,8,7,7,9,10]

array1.sort()
print(array1)

print([*dict.fromkeys(array1)])#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

#OR#
aa = list(dict.fromkeys(array1))
print( aa)#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

- Soudipta Dutta

---

你应该使用内置的set函数：aa = list(set(array1)) - WIP

Answer 9

使用字典数组，将每个项添加为键。 如果一个项是重复的，字典会避免添加它！ 这是最好的解决方案。

int[] numbers = new int[] {1,2,3,4,5,1,2,2,2,3,4,5,5,5,5,4,3,2,3,4,5};
IDictionary<int, string> newArray = new Dictionary<int, string>();

for (int i = 0; i < numbers.count() ; i++) 
{
   newArray .Add(numbers[i] , "");
}

- armin sadeghi

Answer 10

public class RemoveDuplicateArray {
    public static void main(String[] args) {
        int arr[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 2, 3, 4, 9 };
        int size = arr.length;
        for (int i = 0; i < size; i++) {
            for (int j = i+1; j < size; j++) {
                if (arr[i] == arr[j]) {
                    while (j < (size) - 1) {
                        arr[j] = arr[j + 1];
                        j++;
                    }
                    size--;
                }
            }
        }
        for (int i = 0; i < size; i++) {
            System.out.print(arr[i] + "  ");
        }
    }

}

输出 - 1 2 3 4 5 6 7 9

- Onic Team