algorithm - 当有多个重复元素时在数组中查找重复项

Question

当有多个重复元素时，如何在数组中找到重复项？

当数组只有一个重复元素时(例如:1,2,3,4,4,4,5,6,7)则很简单:

int duplicate(int* a, int s)
{ 
    int x = a[0];
    for(int i = 1; i < s; ++i)
    {
        x = x ^ a[i];
    }
    for(int i = 0; i < a[s]; ++i)
    {
        x = x ^ i;
    }
    return x;
}

但如果输入数组包含多个重复元素(例如:1, 2, 2, 2, 3, 4, 4, 4, 5, 6, 7)，上述方法将不起作用。我们怎样才能在 O(n) 时间内解决这个问题？

Answer 1

如果空间不是问题或最大数量很低，您可以简单地使用一种位数组并通过在数字位置设置位来标记所有已经出现的数字。

它是一种具有普通(身份)散列函数的 HashSet。 测试和设置花费 O(1) 时间。