数组的大小为n。除了两个元素之外，数组中的所有元素在[0，n-1]范围内都是不同的。以恒定的时间复杂度，无需使用额外的临时数组即可找出重复的元素。
我尝试过像这样使用 o(n) 。
a[]={1,0,0,2,3};
b[]={-1,-1,-1,-1,-1};
i=0;
int required;
while(i<n)
{
b[a[i]]++;
if(b[a[i]==1)
required=a[i];
}
print required;
如果对数字范围没有限制，即也允许超出范围。是否可以在没有临时数组的情况下获得 o(n) 解决方案。
XOR所有元素加在一起，然后XOR结果与XOR([0..n-1]).
这给你missing XOR repeat; since missing!=repeat，至少设置一位missing XOR repeat.
选择这些设置位之一。再次迭代所有元素，仅XOR具有该位设置的元素。然后迭代自1 to n-1 and XOR那些设置了该位的数字。
现在，该值要么是重复值，要么是缺失值。扫描元素以获取该值。如果找到它，它就是重复元素。否则，它就是缺失值，所以XOR它与missing XOR repeat.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
