LeetCode137 只出现一次的数字II

发表于 | 分类于 |
字数统计: 270 | 阅读时长 ≈ 1

链接： https://leetcode-cn.com/problems/single-number-ii/

题面

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

解法

I和III都做了，回头来看看这个II，发现还是不会做/笑嘻嘻

有一个设计门电路的方法，是通过位运算来进行处理的
但是那个太trick了，看了也记不住
有时间补吧

有一个通用的方法可以解决这个问题，某个元素出现一次，其他元素出现k次

用一个32位的数字，每一位标记出现的次数，如果是不能被3整除则说明这一位要找的数为1
很巧妙的做法
最后得出结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int mask = (1 << i), count = 0;
            for (int idx: nums) {
                if (idx & mask) {
                    count++;
                }
            }
            if (count % 3) {
                ans |= mask;
            }
        }
        return ans;

    }
};