如果一個無序的序列里,有且有一個值,出現了重復。那么如何以N的復雜度找出這個重復值?



0,1,2,..x,x,..98,99  設其為序列s1,其中x重復一次,假設重復的那個x,覆蓋了y
0,1,2,..x,y,..98,99  設其為序列s2,是正確的序列

通過:
sum(s1)-sum(s2)=x-y
求乘積(s1) / 求乘積(s2) = x/y
求得:
x,y

for item in s1:
if (x==item) :
   x是重復值;return;
if (y==item) :
   y是重復值;return;
復雜度:
   N