Missing Number

lc 268

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.

第一用bit运算，思路是既然0到n之间少了一个数，我们将这个少了一个数的数组合0到n之间完整的数组异或一下，那么相同的数字都变为0了，剩下的就是少了的那个数字了

public class Solution {
    public int missingNumber(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int sum = 0;
        for(int i = 0; i < nums.length; i++)
           sum = sum ^ (i + 1) ^nums[i];
        return sum;
    }

}

方法二：binarysearch

    public int missingNumber(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int start = 0;
        int end = nums.length - 1;
        Arrays.sort(nums);
        while(start + 1 < end){
            int mid = (end - start) /2;
            if(nums[mid] > mid){
                end = mid;
            }else{
                start = mid;
            }
        }
        if(nums[start] != start ) return start;
        else if(nums[end] != end) return end;
        else return end + 1;


    }