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?
class Solution { public: int missingNumber(vector<int>& nums) { int res = 0; int numsSize = nums.size(); bool isFind = false; for(int i=0;i<numsSize;i++){ while(nums[i]!=i){ if(nums[i] >= numsSize){ isFind = true; res = i; break; } swap(nums[i],nums[nums[i]]); } } return isFind ? res:numsSize; } };
此外，还有很多好方法，例如，
法1.
先计算sum1=0+1+2+3+...+n,
再计算sum2 = nums[0]+nums[1]+...+nums[n-1];
然后sum1-sum2就是缺失的那个数
法2.排序二分
原文：http://www.cnblogs.com/zengzy/p/5003240.html