137. Single Number II

發表於 | 分類於

problem

從一維陣列找出那個不重複的數字，假設其他數字皆會出現三次

solution

  • 利用2進位表示法，逐一去將第i位元相加，並除以3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(int i=31;i>-1;--i){
            int sum = 0;
            for(int n:nums){
                sum+= (n>>i)&1;
            }
            sum%=3;
            ret+= sum<<i;
        }
        return ret;
        
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)