[leetcode 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.

第一次AC代码：

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

第二次排个序就好了。。。。

class Solution
{
public:
    int missingNumber(vector<int>& nums)
    {
        int sum=nums.size();
        if(sum==0)
            return 0;
         sort(nums.begin(),nums.end());
        for(int i=0;i<sum;++i)
            if(nums[i]!=i)
            return i;
        return sum;
    }
};

原文：http://blog.csdn.net/er_plough/article/details/48129771