268. Missing Number

268. Missing Number

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

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

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

My Solutions:

方法1：先sort，然后依次找到缺少的数字（当前数字和应有的index不相同的情况）

Time: O(nlgn); Space: O(1)

方法2：用HashSet储存所有数字，再找出缺少数字

Time: O(n); Space: O(n)

方法3：位运算，一个数字^自己是0，所以把所有数字和index XOR即可找到缺少数字

Time: O(n); Space: O(1)

Example：

Index	0	1	2	3
Value	0	1	3	4

missing=4∧(0∧0)∧(1∧1)∧(2∧3)∧(3∧4)=(4∧4)∧(0∧0)∧(1∧1)∧(3∧3)∧2=0∧0∧0∧0∧2=2

public class Solution {
    public int missingNumber(int[] nums) {
        int res = nums.length;
        for (int i = 0; i < nums.length; i++) {
            res ^= i;
            res ^= nums[i];
        }
        return res;
    }
}

方法4：数字在0。。。n之间，我们知道对于1。。n，总和是 n * （n + 1）/ 2。所以把nums里所有数字相加，用公式之和减去数字相加之和，即是缺少的数字

Time: O(n); Space: O(1)