Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

1
2
Input: [3,0,1]
Output: 2
1
2
Input: [9,6,4,2,3,5,7,0,1]
Output: 8

不用sum的方法，怎么做？

XOR

一个数a异或同一个数b两次，结果还是那个数a

1
2
3
a ^ a ^ b = b;
a ^ b ^ a = b;
b ^ a ^ a = b;

原因:

  1. 异或就是用二进制来运算，相同为0，不同为1；
  2. 一个数异或自己本身结果为0（全部二进制位相同)
  3. 一个数异或0，结果为这个数本身(0和0异或为0，1和0异或为1，所以结果还是原来的数)

=> 一个数异或另一个数两次相当于异或0一次，所以结果还是这个数本身

1
2
3
4
5
6
7
8
public int missingNumber(int[] nums) {
    int res = nums.length;
    for (int i = 0; i < nums.length; ++i) {
        res ^= i;
        res ^= nums[i];
    }
    return res;
}