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.

4/10/2015 update

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int i = 0;
        while(i < nums.size()){
            if(nums[i] == i || nums[i] == nums.size()){
                i++;
            }
            else{
                int tmp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = tmp;
            }
        }
        for(int i = 0; i < nums.size(); i++){
            if(i != nums[i]){
                return i;
            }
        }
        return nums.size();
    }
};

The key to solve this problem is to put all the elements in right places. (make nums[i] = i). It’s just like a sort algorithm while runs in linear time. I set ‘tail’ variable to -1 to mark it as ’empty’.

//So the size of the array must be n?
//What's the space and time complexity requirements?
//

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int tail = -1;
        int i = 0;
        while(i < nums.size()){
            //element is in the right place
            if(nums[i] == i){
                i++;
            }
            else{
                //element is not in the right place
                if(nums[i] == nums.size()){
                    int tmp = tail;
                    tail = nums[i];
                    nums[i] = tmp;
                }
                //empty slot
                else if(nums[i] == -1){
                    i++;
                }
                else{
                    //swap
                    int tmp = nums[i];
                    nums[i] = nums[nums[i]];
                    nums[tmp] = tmp;
                }
            }
        }
        //check for tail
        if(tail != -1 && tail != nums.size()){
            //swap tail and nums[tail]
            int tmp = tail;
            tail = nums[tmp];
            nums[tmp] = tmp;
        }
        //n is missing
        if(tail == -1) return nums.size();
        
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] != i) return i;
        }
    }
};