首页 🍒LeetCode,🐶算法

题目

Mdbe2zJNvC.png

思路: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;
    }
};



文章评论