java – 在数组中查找不成对的数字

>方法1 – O(n log n)：对数组进行排序.然后,迭代排序数组的元素,一次两个(i = 0,i = 2等).当[i]和[i 1]不相等时 – 或当i 1 == a.length时 – 你知道a [i]是不成对的.
>方法2 – O(n2)：迭代元素.对于每个元素a [i],迭代元素(在嵌套循环中)并查看是否发生a [i] == a [j]而i！= j.如果没有,则[i]未配对.
>方法3 – O(m),其中m是最大和最小元素之间的差异(注意m是Ω(n))：迭代元素,找到最大值和最小值MIN和MAX.创建一个int [] b = new int [MAX-MIN 1].再次迭代元素,为每个元素递增b [a [i] -MIN].然后迭代b;当你发现b [j] == 1时,j是未配对的.

注意：您使用术语“元素整数”,但这不是一个真正的术语.以上假设您的意思是“整数值元素”.如果您实际上是指“元素索引”,则只能使用方法2而无需修改.方法3需要进行一些调整,方法1需要进行大量调整. (当然,一旦你发现只出现一次的值,你可以再次遍历数组以找到该值的索引 – 前提是你仍然拥有原始的数组顺序.)

编辑添加：我不知道我之前是如何错过的 – 我想我在编写Java时不习惯按位运算 – 但最好的解决方案实际上是：

>方法4 – O(n)：计算数组所有元素的按位-XOR,^.这是不成对的元素.你看,XOR是可交换和关联的,所以2 ^ 6 ^ 6 ^ 2 ^ 4 ^ 1 ^ 4与1 ^(2 ^ 2)^(4 ^ 4)^(6 ^ 6)相同;并且x ^ x始终为0,因此对总是取消其他输出.你可以写：

int result = 0;
for(int i : a)
    result ^= i;

计算不成对的元素. (要获取未配对元素的索引,您需要再次遍历数组,查找结果.)