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

题目

思路：Map

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

代码语言：javascript复制

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那么这个数就是所要求的答案的某个二进制位，再把它导出来加起来就得到答案。

代码语言：javascript复制

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

key map

0 人点赞