Single Number II (Medium)

Description

Given an array of integers, every element appears three times except for one. Find that single one.

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

Analysis

我是直接枚举每一位的个数看看是否是3的倍数的。
虽然常数有点大。但是感觉比较通用啊。23333

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//C++
class Solution {
public:
    int singleNumber(int A[], int n) {
        int ans = 0;
        for(int i = 0; i<32 ; i++){  
            int nowbit = (1<<i) , num = 0;
            for(int j = 0 ; j<n ; j++){
                
                if(A[j]&nowbit)
                    num++;
            }
            if(num%3)
                ans|=nowbit;
        }
        return ans;
    }
};