Problem
Given an array contains N numbers of 0 .. N, find which number doesn't exist in the array.
Example
Given N = 3 and the array [0, 1, 3], return 2.
Note
找第一个缺失的数，可以用求和相减或二分法查找，也可以用位运算XOR来做。
求和相减是先求出0到N这个等差数列的和，再减去实际数组的和，就是缺失的数，第二种方法是，只要先按顺序排列好[0, 1, 2, 3, 4, ...]，用二分法找到第一个和A[i]不相等的数i就可以了。 Solution
1. 二分法
public class Solution { public int findMissing(int[] A) { int len = A.length; Arrays.sort(A); int left = 0, right = len - 1; while (left < right) { int mid = left + (right - left) / 2; if (A[mid] > mid) { right = mid - 1; } else { left = mid + 1; } } return A[left] == left ? left + 1 : left; }} 2. 求和相减法
public class Solution { public int findMissing(int[] A) { int len = A.length; int sum = 0; for (int i = 0; i < len; i++) { sum += A[i]; } int targetsum = len * (len + 1) / 2; //0, 1, 2,...,len, 共len+1个数，多加了一个len return targetsum - sum; }} 3. 异或法
public class Solution { public int findMissing(int[] nums) { int x = 0; for (int i = 0; i <= nums.length; i++) { x ^= i; } for (int i = 0; i < nums.length; i++) { x ^= nums[i]; } return x; }}