LeetCode 268. Missing Number

268. Missing Number

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.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

【题目分析】

从0,1,2,...,n这n+1个数中选择n个数，找出这n个数中缺失的那个数。

【思路】

1. 累加

计算1+2+...+n. 用和值减去数组中数的和值，最后的差就是我们要的结果。这个过程中要防止溢出。

2. 异或

异或运算有一个性质，x^y^y=x. 结果与x和y的顺序无关。我们把0～n与数组中的数都异或到一起，那么最后的结果就是缺失的那个数。

3. 二分查找

把数组排序，用二分查找来找到缺失值。

【java代码1】

 1 public class Solution {
 2     public int missingNumber(int[] nums) {
 3         int res = 0;
 4         for(int i = 1; i <= nums.length; i++) {
 5             res += (i-nums[i-1]);
 6         }
 7         
 8         return res;
 9     }
10 }

【java代码2】

1 public int missingNumber(int[] nums) { //xor
2     int res = nums.length;
3     for(int i=0; i<nums.length; i++){
4         res ^= i;
5         res ^= nums[i];
6     }
7     return res;
8 }

【java代码3】

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