有人用异或法解第二题吗。。

Discuss / Java / 有人用异或法解第二题吗。。

Back

Topic source

#1 Created at ... [Delete] [Delete and Lock User]

private static int findMissingNumber(int start, int end, List<Integer> list) {

int s = 0;

int x = start;

for(int i : list) {

s = s^x^i;

x++;

}

return s^0^x;

}

#2 Created at ... [Delete] [Delete and Lock User]

朋友，您的方法太巧妙了。能讲讲思路吗。

#3 Created at ... [Delete] [Delete and Lock User]

最后返回时异或0有什么作用吗？

#4 Created at ... [Delete] [Delete and Lock User]

这方法相当于start加到end减去list所有元素之和；

#5 Created at ... [Delete] [Delete and Lock User]

我应该明白您的意思了，每一个数对自己异或为零，将start到end和list里的数全部异或，那么相同的数会置零，唯一一个没有被归零的数就是在list里被删除的数。

#6 Created at ... [Delete] [Delete and Lock User]

都没说清楚，这种解法的巧妙在于，利用了异或算法的交换律和结合律。

计算s的过程应该看成一个整体（包括最后一步），举个例子，原数列是1、2、3，打乱+随机去掉以后变成了3、2，那么本解答中的s计算过程就变成了：1^3^2^2^3，经过交换律和结合律：1^(2^2)^(3^3)=1^0^0=1，这样就找出了去掉了哪个数字，也就是1。

#7 Created at ... [Delete] [Delete and Lock User]

高手！受教了。

这里用到位级运算异或的两个性质和两个运算定律：

另外，由于每次循环计算 s 在 x++ 操作之前，所以最后一个 x = 20 没有进行异或计算，循环外再将 s 和 x 进行一次异或计算，收工。