Find the Missing Number

Given an array contains N numbers of 0 .. N, find which number doesn't exist in the array.

Do it in-place with O(1) extra memory and O(n) time.

从N+1个数里面选N个，找漏掉了哪一个。 http://www.lintcode.com/en/problem/find-the-missing-number/

Discussion

跟First Missing Positive问题类似，用bucket sort，方案1，O(n)space for buckets。方案2，利用数组本身。

Solution 1:

class Solution {
public:
    /**    
     * @param nums: a vector of integers
     * @return: an integer
     */
    int findMissing(vector<int> &nums) {
        // write your code here
        int n = nums.size();
        vector<int> sorted(n+1, -1);
        for(int i=0; i<n; i++) {
            if (nums[i] >=0 && nums[i] <=n) {
                sorted[nums[i]] = nums[i];//桶排序的核心
            }
        }
        for(int i=0; i<n+1; i++) {
            if(sorted[i] != i)
                return i;
        }
        //return n+1;
    }
};

Solution 2

class Solution {
public:
    /**    
     * @param nums: a vector of integers
     * @return: an integer
     */
    int findMissing(vector<int> &nums) {
        // write your code here
        int n = nums.size();
        for(int i=0; i<n; i++) {
            while (nums[i] != i) {
                if(nums[i]==n || nums[i] == nums[nums[i]]) break;//第一个情况容易漏掉
                swap(nums[nums[i]], nums[i]);
            }
        }
        for(int i=0; i<n; i++) {
            if(nums[i] != i)
                return i;
        }
        return n;
    }
};