Skip to content

Single Number II⚓︎

Link

Description⚓︎

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

  • Input: nums = [2,2,3,2]
  • Output: 3

Example 2:

  • Input: nums = [0,1,0,1,0,1,99]
  • Output: 99

Constraints:

  • 1 <= nums.length <= 3 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
  • Each element in nums appears exactly three times except for one element which appears once.

Solution⚓︎

Way 0: General Solution⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
private:
    int find(const vector<int>& nums, int m) {
        vector<int> counts(32, 0);
        for (int x : nums) {
            for (int i = 0; i < 32; i++) {
                counts[i] += (x >> i) & 1;
            }
        }

        int res = 0;
        for (int i = 0; i < 32; i++) {
            if (counts[i] % m) {
                res |= 1 << i;
            }
        }
        return res;
    }

public:
    int singleNumber(vector<int>& nums) {
        return find(nums, 3);
    }
};

Way 1⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int cnt = 0;
            for (int num : nums) {
                cnt += num >> i & 1;
            }
            ans |= cnt % 3 << i;
        }
        return ans;
    }
};
  • Time complexity: \(O(n\log 2^{32})\);
  • Space complexity: \(O(1)\).

Way 2⚓︎

See reference (Chinese).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int two = 0, one = 0;
        for (auto x : nums) {
            one = (one ^ x) & ~two;
            two = (two ^ x) & ~one;
        }
        return one;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(1)\).