Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
Example 1:
Input: [3,0,1]
Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
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 sum = 0;
for(int i=0; i<nums.size(); i++){
sum += nums[i];
}
return (1 + nums.size()) * nums.size() / 2 - sum;
}
};
Runtime: 36 ms, faster than 25.15% of C++ online submissions for Missing Number.
Memory Usage: 9.7 MB, less than 93.72% of C++ online submissions for Missing Number.
思路
- Miss Number = sub（数列求和, 数组加和）
优化
- 二进制异或操作，相同的为0，不同的为1，被保留下来。
int missingNumber(vector<int>& nums) {
int res = 0;
for(int i = 0; i < nums.size(); ++i){
res ^= (i + 1) ^ nums[i];
}
return res;
}
Runtime: 24 ms, faster than 98.06% of C++ online submissions for Missing Number.
Memory Usage: 9.8 MB, less than 52.19% of C++ online submissions for Missing Number.
