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.

For example,
Given nums = [0, 1, 3] return 2.

题目含义：从0到n选取了n个数，其中只有一个丢失了，找到丢失的数字

方法一:

利用异或运算的规律 0 ^ a = a，以及 a ^ b ^ a = b

1     public int missingNumber(int[] nums) {
2        int xor = 0, i = 0;
3        for (i = 0; i < nums.length; i++) {
4            xor = xor ^ i ^ nums[i];
5        }
         这里i是数组索引，所以从0到n-1的数字都被异或到xor中了
         经过遍历后，0到n中除了缺少的数字，都被异或进去了， 
         此时xor=（n-1）^缺少数字^n
6        return xor ^ i;  //消除数字n
7     }

方法二排序好后依次检查

 1     public int missingNumber(int[] nums) {
 2         if (nums.length == 0) return 0;
 3         if (nums.length == 1 ) return (nums[0]+1)%2;
 4         Arrays.sort(nums);
 5         for (int i=0;i<nums.length-1;i++)
 6         {
 7             if (nums[i]+1 != nums[i+1]) return nums[i]+1;
 8         }
 9         if(nums[0] > 0) return 0; //头部缺少数字0
10         else return nums[nums.length-1] + 1;  //尾部缺少数字n    
11     }

方法三：

计算出不缺少数字情况下的数字总和，然后减去当前的数字总和，即为缺少的数字

这里用到了等差数列求和公式 sum = (n * (n + 1))/ 2

1     int missingNumber(int[] nums) {  
2         int sum = 0;    
3         for(int num: nums)  
4             sum += num;    
5         int n = nums.size();    
6         return (n * (n + 1))/ 2 - sum;    
7     }

类似题目：

442. Find All Duplicates in an Array

287. Find the Duplicate Number

448. Find All Numbers Disappeared in an Array