【算法 | 位运算No.1】leetcode268. 丢失的数字

点击直接跳转到该题目

1️⃣题目描述

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例1：

示例2：

示例3：

示例4：

注意：

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• nums 中的所有数字都 独一无二

2️⃣题目解析

总共有三种解法（哈希、位运算、高斯求和）。

这里只对位运算和高斯求和进行解释。

位运算求解原理：

• 相同数组进行异或结果为0
• 0 ^ num = num

高斯求和原理：

• 把[0,n]的和记为sum1
• 把数组nums中所有的元素之和记为sum2
• 丢失的数字即为sum1 - sum2

3️⃣解题代码

解法1（高斯求和）：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size(),sum1 = 0,sum2 = 0;

        for(int i = 0;i < n;i++) sum1 += nums[i];
        for(int i = 0;i <= n;i++) sum2 += i;

        return sum2 - sum1;   
    }
};

解法2（位运算）：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size(),ret = 0;
        for(auto x : nums) ret ^= x;
        for(int i = 0;i <= n;i++) ret ^= i;
        return ret;
    }
};