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.

 

解题思路：

题目意思是给出一个数组，是从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;     } };