APPROACH: BINARY SEARCH

其實二分搜索很多地方都又變種，有時候不一定是要「找到目標」(nums[mid] == value那種)，比如這個，思路這樣的：

1. 排序后，nums[mid] 如果等于mid，說明缺少的那個數(shù)在mid的右邊，那么left = mid + 1。如：
   0123467
2. 如果nums[mid]>mid,說明缺少的那個數(shù)在mid左邊，那么right = mid;

注意終止條件，left<right，而不是標準二分的<=。因為left == right 的情形就已經是找到了。

public int missingNumber(int[] nums) { //binary search
    Arrays.sort(nums);
    int left = 0, right = nums.length, mid= (left + right)/2;
    while(left<right){
        mid = (left + right)/2;
        if(nums[mid]>mid) right = mid;
        else left = mid+1;
    }
    return left;
}

APPROACH: SUM

我想到了這個方法。

        if (nums == null || nums.length == 0) return -1;
        int total = 0;
        for (int i : nums) {
            total += i;
        }
        return (1 + nums.length) * (nums.length) / 2 - total;

//or：
    int len = nums.length;
    int sum = (0+len)*(len+1)/2;
    for(int i=0; i<len; i++)
        sum-=nums[i];
    return sum;

APPROACH : XOR

我又沒想到。明明跟SINGLE NUMBER和389那么像。。還是用得少。注意0異或任何數(shù)都等于0。

        //0異或任何數(shù)都等于0
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i] ^ i;
        }
        return res ^ (nums.length );