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

    
        标签：
        
            剑指 Offer
        
    发布于：2022-02-27 17:29:45
    编辑于：2022-02-27 17:50:41
    浏览量：854

概述

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

有意思哦，出现 3 次的话，要怎么搞嘞。

暴力法

这次用一个哈希表来记录。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> m;
        for (auto n : nums) m[n] ++;
        for (auto iter = m.begin(); iter != m.end(); iter ++) {
            if (iter->second == 1) return iter->first;
        }
        return 0;
    }
};

位运算

所有数字的所有位对应相加，其中不能被 3 整除的即目标数字的位。

这是看的剑指 Offer 上的思路。

实现时，注意 if (i != 31) mask = mask << 1; 这里，如果左移 32 次将导致 runtime error: left shift of negative value -2147483648。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> count(32);
        for (auto n : nums) {
            int mask = 1;
            for (int i = 0; i < 32; i ++) {
                if (n & mask) count[i] ++;
                if (i != 31) mask = mask << 1;
            }
        }
        int ans = 0;
        for (int i = 31; i >= 0; i --) {
            ans = ans << 1;
            ans += count[i] % 3;
        }
        return ans;
    }
};

Links: sword-offer-56-2