题目
给定一个数组,里面数字是从0到n,但是缺了一个数,找出缺的数字。
Input:[3,0,1]
Output: 2
Input:[9,6,4,2,3,5,7,0,1]
Output: 8
Input:[0]
Output: 1
Input:[1]
Output: 0
思路1
使用n+1的数组做标记,有这个数就标记为1,没有就标记为0。最后找出为0的数。
int missingNumber1(vector<int>& nums) {
vector<int> vec(nums.size()+1,0);
for (int a : nums) {
vec[a] = 1;
}
for (int i = 0;i < vec.size();i++) {
if (vec[i] == 0) {
return i;
}
}
return (int)nums.size();
}
思路2
位运算,异或运算。分别对前n个数做异或,对给定数做异或,然后对两者再做异或,即可找到缺失的数。
int missingNumber(vector<int>& nums)
{
if (nums.empty()) return 0;
int all = 0x0;
int cur = 0x0;
for (int i = 0; i < nums.size()+1; i++) {
all = all ^ i;
if (i != nums.size()) {
cur = cur ^ nums[i];
}
}
return (all ^ cur);
}
总结
神奇的异或操作,进行两次异或,负负得正的原理。
网友评论