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

Tag: 剑指-Offer Posted on 2022-02-27 17:19:52 Edited on 2022-02-27 17:28:10 Views: 172

概述

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};
    }
};

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