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

Tag: 剑指-Offer Posted on 2022-02-27 17:29:45 Edited on 2022-02-27 17:50:41 Views: 130

概述

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

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