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.
解题思路：
题目意思是给出一个数组，是从0,1,…,n中取出n个数，找出不在这个数组中的数。
方法一：sum
|
class Solution { public: // 36ms int missingNumber(vector<int>& nums) { int n=nums.size(); if(n==0)return 0; int s=n&1?((n+1)>>1)*n:(n>>1)*(n+1); for(int i=0;i<n;i++) s-=nums[i]; return s; } }; |
方法二：xor
n个数异或，同时与0,1,2,3…,n这几个数异或，这样在数组中出现的数一定出现了两次，对异或结果没有影响，只有那个不在数组中的数出现一次。
|
class Solution { public: // 32ms int missingNumber(vector<int>& nums) { int n=nums.size(); if(n==0)return 0; if(n==1)return 1-nums[0]; int s=0; for(int i=1;i<=n;i++) s^=i^nums[i-1]; return s; } }; |
方法三：binary search
首先对数组进行排序，再二分查找。。。。有点不好理解。。
|
class Solution { public: // 68ms int missingNumber(vector<int>& nums) { int n=nums.size(); if(n==0)return 0; sort(nums.begin(),nums.end()); int l=0,r=n; int mid; while(l<=r){ mid=l+((r-l)>>1); if(nums[mid-1]+1!=nums[mid])return nums[mid-1]+1; if(nums[mid]!=mid)r=mid-1; else l=mid+1; } return mid; } }; |
原文：http://www.cnblogs.com/olivelv/p/5235680.html