268.丢失的数字

发布时间 2023-12-14 12:35:25作者: owmt

给定一个包含 [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;
    }  
};