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

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

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

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

PS [你不应该使用排序]

如果您知道可能的输入域是什么,那么有一个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;

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

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

最简单的解决方案

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

一个总和(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个以上)
 
并且最后检查找到候选人,如果他们真的出现在阵列两次.

        
我认为这个解决方案并不完美.看一下这个数组:int A [] = {2,0,6,1,1,4,2,3,5}; 其中n = 9.我得到的结果是{1,0}  - 尽管它确实适用于数组示例,OP给出了...... 
如果p和q都是4的倍数和许多其他情况,则该解决方案不起作用. 

3> sdfx..：
您知道您的数组包含从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

        

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

        
我认为哈希表比数组更好,因为你不需要在创建它们时指定大小,这与数组不同 

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

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

        

6> CMS..：
查看关于该主题的这篇旧的但很好的论文:


寻找重复元素 (PDF)