剑指 Offer 56 - I 数组中数字出现的次数

概述

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

要求时间复杂度是O(n)，空间复杂度是O(1)。

之前有一道类似的，只有一个数字出现了一次，其他都出现了两次，当时那道题是用异或求出来的。

暴力遍历

用一个 set 来记录有没有出现过。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        set<int> s;
        for (auto n : nums) {
            if (s.count(n) != 0) {
                s.erase(n);
            } else {
                s.insert(n);
            }
        }
        vector<int> ans(s.begin(), s.end());
        return ans; 
    }
};

可以看到上面的暴力遍历方法其实不针对两个数字，多个数字也是 okay 的， 显然我们可以利用两个数字这一点来进行优化。

异或分组

看了《剑指 Offer》，同样是先异或，得到一个非 0 的数，从中选出一个为 1 的 bit， 显然这两个数字在该 bit 是不同的，那么按照该 bit 的取值对所有数字分组，这两个数字必然被分开， 其他两两相同的数字自然被分到同一个组，之后对这两个组的数字分别 XOR 求得那两个数字。

实现的时候注意位运算的优先级较低，不放心的话就套括号好咯。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int t = nums[0];
        for (int i = 1; i < nums.size(); i ++) t ^= nums[i];
        int n = 0;
        while (t % 2 == 0) {
            t = t >> 1;
            n ++;
        }
        int a = 0, b = 0;
        for (auto num : nums) {
            if ((num >> n) % 2 == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return {a, b};
    }
};

Links: sword-offer-56-1

未经允许，禁止转载，本文源站链接：https://iamazing.cn/