给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。(所有数字不重复)
示例
输入: nums = [3,0,1]
输出:2
思路:
可以排序后遍历查找缺失的数字,也可以用求和公式计算 [0,n] 的和减去nums数组的和,也可以使用哈希集合。还有一种方法就是使用异或,先对数组nums中的每个元素进行异或,然后再对 [0, n] 中的每个数进行异或运算,最后的结果就是缺失的数字。时间复杂度为O(n)。(x⊕x=0、x⊕0=x)
代码:
class Solution {
public:
int missingNumber(vector<int>& nums) {
int res = 0;
for(int i = 0; i < nums.size(); ++i){
res ^= nums[i];
}
for(int i = 0; i <= nums.size(); ++i){
res ^= i;
}
return res;
}
};
标签:数字,nums,int,res,异或,丢失,数组,268
From: https://www.cnblogs.com/owmt/p/17900749.html