leetcode 消失的数字

前言

• 异或的性质
• lowbit 算法

其他的几个注意点, least significant bit (lsb)

1. int a = INT32_MIN;, 通过观察 INT32_MIN 的二进制形式, 其 lowbit 等于自身
2. a == -a;, -a 虽然会溢出, 但仍会被解析为 INT32_MIN, 所以相等
3. a == (a & -a);, 自身与自身逐位相与, 得到的还是自身

这个题还有扩展. 比如, 一个数组中, 有两个数出现了奇数次, 其他数出现了偶数次, 请找出两个出现奇数次的数并返回.

系统中存储的数都是二进制的补码.lsb 单纯的就得出, 不存在的两个数异或结果的最低位那个 1, 即 lsb 是那个除了 L 位 1, 其它位均为 0 的一个二进制数 (x1, 跟 x2 的分类标准就是 L 位是否为 1). 第 L 位 1 的话, 根据异或运算能倒推 type1 或者 type2 肯定有一个值存在 L 位为 1 的情况, 即 type1 跟 type2 分别在 x1 跟 x2 类里. 在 x1 跟 x2 类里分别刨除重复的数 (因为重复的数异或结果为 0), 剩下的就是 type1, type2 了.

最低有效位 (Least Significant Bit). 通过 xorSum & -xorSum 获取最低有效位, 表明只出现一次的那两个数中, 有一个数的二进制表示的 lsb 为 1, 另一个数的二进制表示的 lsb 为 0. 这样就可以按照为 0 和 1 两类, 与集合 nums 和 [1, n] 再异或运算一次. 最终出现两次的通过异或运算全部去掉, 留下的只出现一次的就是分为两类的 x1 和 x2.

k = xor & (-xor).k 表示 xor 的二进制表示只保留最右的一个 1. 其他为全部置 0 感觉这一点非常关键!

要是要求缺失的三个数呢?

位运算相关题目

• https://leetcode.cn/problems/single-number-iii/

原来的数一共有多少位

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {

    }
};

题目说的是 1 ~ n 个数字, 但是只提供了一个缺少两个数的数组: nums, 所以原来的数是从 1 ~ nums.size()+1, 可恶, 我居然连这个都没有想到.

等差数列

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size() + 2;
        long sum = 0;
        for (auto x: nums) sum += x;

        // 两数之和为 sumTwo, sumTwo / 2 的意思是, 其中一个数肯定小于等于 sumTwo / 2
        // 由于缺失的两个数肯定不是一样的, 所以一定是一个数小于等于 sumTwo / 2
        int sumTwo = n * (n + 1) / 2 - sum, limits = sumTwo / 2;
        sum = 0;
        // 对 1 ~ limits 的数求和, 这个时候肯定会缺少一个数字
        for (auto x: nums)
            if (x <= limits) sum += x;
        int one = limits * (limits + 1) / 2 - sum;
        return {one, sumTwo - one};
    }
};

位运算

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int xorsum = 0;
        int n = nums.size() + 2;
        for (int num : nums) {
            xorsum ^= num;
        }
        for (int i = 1; i <= n; i++) {
            xorsum ^= i;
        }
        // 防止溢出
        int lsb = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum));
        int type1 = 0, type2 = 0;
        for (int num : nums) {
            if (num & lsb) {
                type1 ^= num;
            } else {
                type2 ^= num;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (i & lsb) {
                type1 ^= i;
            } else {
                type2 ^= i;
            }
        }
        return {type1, type2};
    }
};

原地 hash

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // 在 nums 后面补上 3 个数
        for (int i = 0; i < 3; i++) nums.push_back(-1);

        for (int i = 0; i < nums.size(); i++)
            // 注意这里是个 while 循环
            while (i != nums[i] && nums[i] != -1)
                swap(nums[i], nums[nums[i]]);

        vector<int> ans;
        for (int i = 1; i < nums.size(); i++)
            if (nums[i] == -1) ans.push_back(i);
        return ans;
    }
};