APPROACH: BINARY SEARCH
其实二分搜索很多地方都又变种，有时候不一定是要「找到目标」(nums[mid] == value那种)，比如这个，思路这样的：
- 排序后，nums[mid] 如果等于mid，说明缺少的那个数在mid的右边，那么left = mid + 1。如：
0123467 - 如果nums[mid]>mid,说明缺少的那个数在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异或任何数都等于0。
//0异或任何数都等于0
int res = 0;
for (int i = 0; i < nums.length; i++) {
res ^= nums[i] ^ i;
}
return res ^ (nums.length );
