本題源自leetcode 268
-------------------------------------------------------------
思路:用 異或 操作符、倆個相同的數異或等于0 ,與 0 異或等于自身。
代碼:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int res = n;
for(int i = 0;i < n;i++){
res ^= i;
res ^= nums[i];
}
return res;
}
思路2: 排序 二分查找。排序後,對應的數在數組對應的位置上
代碼:
int missingNumber(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(),nums.end());
int left = 0;
int right = n;
while(left < right){
int mid = (left + right) >> 1;
if(mid < nums[mid])
right = mid;
else
left = mid + 1;
}
return left;
}
思路3: 求和法。
代碼
int missingNumber(vector<int>& nums) {
int sum = 0;
int n = nums.size();
for(int num : nums){
sum += num;
}
return (n * (n + 1))/2 - sum;
}