LC 137. 只出现一次的数字 II（位运算）

SakuraTears

发布于 2022-01-13 14:59:28

40800

代码可运行

文章被收录于专栏：从零开始的Code生活从零开始的Code生活

运行总次数：0

代码可运行

题目

思路：Map

遍历数组然后把每个数存到map里，然后再在map里找到values == 1的key就是答案。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        map<int, int> mp;
        for (int i : nums) {
            mp[i]++;
        }
        for (auto it : mp) {
            if (it.second == 1) {
                return it.first;
            }
        }
        return 0;
    }
};

思路：位运算

只有一个数出现了一次，其他数都出现了三次，那么别的数的每个二进制位加起来的和除3一定为0。

所以如果某个二进制位取余3不为0那么这个数就是所要求的答案的某个二进制位，再把它导出来加起来就得到答案。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int num = 0;
            for (int n : nums) {
                num += ((n >> i) & 1);
            }
            if (num % 3 == 1) {
                res |= (1 << i);
            }
        }
        return res;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021年04月30日，如有侵权请联系 cloudcommunity@tencent.com 删除

key