NC101：缺失数字

解法1：数组/哈希
用一个数组/哈希标记出现过的数字，再遍历这个数组看是否有为0的值，即为缺失的值。
数组：

class Solution {
    public int missingNumber(int[] nums) {
        int [] flag = new int[nums.length + 1];
        int ans = 0;
        for( int one : nums ) flag[one]++;
        for( int i = 0 ; i < flag.length ; i++ ){
            if( flag[i] == 0 ){
                ans = i;
                break;
            }
        }
        return ans;
    }
}

哈希：

class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> numSet = new HashSet<Integer>();
        for (int num : nums) numSet.add(num);

        int expectedNumCount = nums.length + 1;
        for (int number = 0; number < expectedNumCount; number++) {
            if (!numSet.contains(number)) {
                return number;
            }
        }
        return -1;
    }
}

解法2：排序
排序后看在不在那个位置上就行了

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            if(i==nums[i])
                continue;
            return i;
        }
        return nums.length;
    }
}

解法3：位运算
一般对数字的处理，都可以想想位运算
用原数组也就是（0,n）来跟这个nums数组做位运算，可以使很多数字抵消

很明显，2是我们要获得的答案，但是还有个4需要我们抵消，4是什么？
是数组的长度！那么每次我们每次再把数组长度手动放进去异或抵消就可以得到答案了

class Solution {
    public int solve (int[] a) {
        // write code here
        int n=a.length;
        for(int i=0;i<a.length;i++){//不能再用n，会变，不再是数组a的长度
            n^=i^a[i];
        }
        return n;
    }
}

解法4：二分
输入有序，二分查找，注意边界：

    public int solve(int[] a) {
        int l = 0, r = a.length - 1;
        while(l < r) {
            int mid = (l+r)/2;
            if(a[mid] == mid) l = mid + 1;
            else if(a[mid] > mid) r = mid;
        }
        return l;
    }