如果一个无序的序列里,有且有一个值,出现了重复。那么如何以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