在数组中查找两个重复数字的算法,无需排序

Question

有一个大小为n的数组(数字介于0和n - 3之间),只重复2个数字.元素随机放置在数组中.

例如,在{2,3,6,1,5,4,0,3,5} n = 9,重复数为3和5.

找到重复数字的最佳方法是什么？

PS [你不应该使用排序]

Answer 1

如果您知道可能的输入域是什么,那么有一个O(n)解决方案.例如,如果输入数组包含0到100之间的数字,请考虑以下代码.

bool flags[100];
for(int i = 0; i < 100; i++)
    flags[i] = false;

for(int i = 0; i < input_size; i++)
    if(flags[input_array[i]])
         return input_array[i];
    else       
        flags[input_array[i]] = true;

当然还有额外的内存,但这是最快的.

Answer 2

好吧,好像我只是不能休息一下:)

最简单的解决方案

int A[N] = {...};

int signed_1(n) { return n%2<1 ? +n : -n;  } // 0,-1,+2,-3,+4,-5,+6,-7,...
int signed_2(n) { return n%4<2 ? +n : -n;  } // 0,+1,-2,-3,+4,+5,-6,-7,...

long S1 = 0;  // or int64, or long long, or some user-defined class
long S2 = 0;  // so that it has enough bits to contain sum without overflow

for (int i=0; i<N-2; ++i)
{
   S1 += signed_1(A[i]) - signed_1(i);
   S2 += signed_2(A[i]) - signed_2(i);
} 

for (int i=N-2; i<N; ++i)
{
   S1 += signed_1(A[i]);
   S2 += signed_2(A[i]);
} 

S1 = abs(S1);
S2 = abs(S2);

assert(S1 != S2);  // this algorithm fails in this case

p = (S1+S2)/2;
q = abs(S1-S2)/2;

一个总和(S1或S2)包含具有相同符号的p和q,另一个总和 - 具有相反的符号,所有其他成员被消除.
S1和S2必须有足够的位来容纳和,因为abs()算法不能代表溢出.

如果abs(S1)== abs(S2)那么算法失败,尽管这个值仍然是p和q之间的差值(即abs(p-q)== abs(S1)).

以前的方案

我怀疑有人会在现场遇到这样的问题;)
我想,我知道老师的期望:

让我们得到数组{0,1,2,...,n-2,n-1},
给定的一个可以通过用未知的p和q(较少的顺序)替换最后两个元素n-2和n-1来产生.

因此,元素之和将是(n-1)n/2 + p + q - (n-2) - (n-1)
平方和(n-1)n(2n-1)/ 6 + p ^ 2 + q ^ 2 - (n-2)^ 2 - (n-1)^ 2

简单的数学依旧:

  (1)  p+q = S1  
  (2)  p^2+q^2 = S2

当然,你不会解决它,因为数学课教授解方形方程.

首先,计算模2 ^ 32的所有模数,即允许溢出.
然后检查对{p,q}:{0,S1},{1,S1-1} ...对表达式(2)以找到候选者(由于模和平方可能有2个以上)
并且最后检查找到候选人,如果他们真的出现在阵列两次.

Answer 3

您知道您的数组包含从0到n-3的每个数字以及两个重复的数字(p&q).为简单起见,我们暂时忽略0-case.

您可以计算数组上的总和和产品,结果是:

1 + 2 + ... + n-3 + p + q = p + q + (n-3)(n-2)/2

所以如果你从整个数组的总和中减去(n-3)(n-2)/ 2,你就得到了

sum(Array) - (n-3)(n-2)/2 = x = p + q

现在对产品做同样的事情:

1 * 2 * ... * n - 3 * p * q = (n - 3)! * p * q

prod(Array) / (n - 3)! = y = p * q

你现在有这些条款:

x = p + q

y = p * q

=> y(p + q) = x(p * q)

如果你改变这个术语,你应该能够计算p和q

Answer 4

将每个元素插入到一个set/hashtable中,首先检查它是否已经在其中.

Answer 5

您可以利用sum(array)=(n-2)*(n-3)/ 2 +两个缺失数字这一事实.

编辑:正如其他人所说,结合方格和,你可以使用它,我只是有点慢搞清楚.

Answer 6

查看关于该主题的这篇旧的但很好的论文:

• 寻找重复元素 (PDF)

Answer 7

对数组进行排序似乎是最好的解决方案。简单的排序将使搜索变得微不足道，并且会花费更少的时间/空间。

否则，如果您知道数字的域，请创建一个包含多个存储桶的数组，并在遍历该数组时递增每个存储桶。像这样的东西：

int count [10];

for (int i = 0; i < arraylen; i++) {
    count[array[i]]++;
}

然后只需在数组中搜索任何大于 1 的数字。这些是具有重复项的项目。只需要遍历一次原始数组和遍历一次计数数组。