137. Single Number II

发表于 | 分类于

Given an 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?

解法1： O(N) Time + O(1) Space

主要的思路是对于每一位（32中的一位），如果一个数字出现三次的话，该位出现次数为1.
如果统计每一个位数上的出现次数，再对3取余，那么剩下的每一个位子上的1就是只出现一次的数。
这个思想也可以递推到其他的出现频率题上。

lang: java
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 {
    public int singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num : nums) {
                if (((num >> i) & 1) == 1) {
                    count++;
                }
            }
            count = count % 3;
            if (count != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
}