137.Single Number II

Tags: Medium Bit Manipulation

Links: https://leetcode.com/problems/single-number-ii/

---

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

---

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;

        for (int i = 0; i < 32; ++i){
            int mask = 1 << i;
            int cnt = 0;

            for (auto e : nums){
                if (e & mask) ++cnt;
            }

            if (cnt % 3) result |= mask;
        }

        return result;
    }
};

思路：每一位判断是否是1，如果某一位上1的个数不是3的倍数，则此位由单独的数字贡献，保留下来。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        const int W = sizeof(int) * 8; //一个整数的bit数，即整数字长
        int count[W]; // count[i]表示在i位出现的1的次数
        fill_n(&count[0], W, 0);
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < W; j++) {
                count[j] += (nums[i] >> j) & 1;
                count[j] %= 3;
            }
        }

        int result = 0;
        for (int i = 0; i < W; i++) {
            result += (count[i] << i);
        }

        return result;
    }
};