描述 Description

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?

[Missing Number]

分析 Analysis

本题的意思是，从1到n的整数，其中某个数丢失了，替代它的是0。要我们从0到n之间取出n个不同的数，找出漏掉的那个。

方法1

我们可以用公式计算出从1到n的和，减去实际数组的总和，差值就是那个丢失的数。注意实现的时候，遍历时需要同时记录最大值n（或者在c++等等输入的vector数据中直接通过nums.size()计算出来），积累和，以及是否有0（积累和为n*(n-1)/2，既可能是0漏掉也可能是n+1漏掉。不过实现时候可以稍微使用一点技巧。

方法2（推荐）

类似"single number"利用异或位运算。首先将0到n这些数进行异或运算，然后对输入的数组进行异或运算，最后将两个结果进行异或运算，结果便是漏掉的数字，因为其他数字在两个数组中都是成对出现的，异或运算会得到0。

Note: 从CPU指令所耗费的时钟周期来看，比加法更高效率的运算是异或(XOR)运算。所以其效率应该比方法1好。

方法3

二分查找。首先把数组排序，设中间元素为nums[mid]，如果nums[mid]的值大于其下标，说明丢失的数字在左边，反之则在右边。时间复杂度O(nlogn)，比前面两个方法慢，但是如果题目给的数组是事先排好序的，那么复杂度就是O(log n)，所以这个方法只是用于题目说明是有序时才比XOR更有效。

代码 Code

方法1

int miss = 0, i = 0;
for (int num : nums)
    miss += ++i - num;
return miss;

或者

int missingNumber(vector<int>& nums) {
    long n = nums.size();
    return n * (n+1) / 2 - accumulate(begin(nums), end(nums), 0);
}

方法2

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int result = nums.size();
        int i=0;

        for(int num:nums){
            result ^= num;
            result ^= i;
            i++;
        }

        return result;
    }
};

方法3（java）

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;
}