Description
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?
My solution
//
// Created by Fennnnng on 2017-08-29.
//
#include<algorithm>
using namespace std;
// #include<algorithm>
// class Solution {
// public:
// int missingNumber(vector<int>& nums) {
// sort(nums.begin(),nums.end());
// if(nums[0]!=0) return 0;
// for(int i=1;i<nums.size();i++){
// if(nums[i]-nums[i-1]!=1) return i;
// }
// return nums.size();
// }
// };
class Solution {
public:
int missingNumber(vector<int>& nums) {
int numSize=nums.size();
int sum=0;
for(int i=0;i<numSize;i++) sum+=nums[i];
return numSize*(numSize+1)/2-sum;
}
};上面注释掉的代码是第一种方法,可以AC,但因为sort复杂度为nlgn,不符合题意中的O(n)的要求. sort之后如果采用二分查找可以做优化, 但是总体还是nlgn.
为寻找更高效方法,思考0,1,2...n的特点:
性质1. 每个数都是不同的
性质2. 刚刚好差了1
我的第2种方式利用了性质2, 没有挖掘出性质1. 复杂度已经达到了O(n).
Discuss
充分利用性质1和性质2, 就有XOR的解决方案了:
// Java
public int missingNumber(int[] nums) { //xor
int res = nums.length;
for(int i=0; i<nums.length; i++){
res ^= i;
res ^= nums[i];
}
return res;
}注意到res初始值为length
- 每个数都是不同的,故采用A^A抵消的这个trick(前面leetcode有所提及)
A^A=0; A^0=A 用作两两抵消
- i递增就是nums中的元素是利用了性质2
