LC.P136[只出现一次的数字II]

方法一：位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int cnt = 0;
            for (int num : nums) {
                cnt += num >> i & 1;
            }
            cnt %= 3;
            ans |= cnt << i;
        }
        return ans;
    }
}
  • 时间复杂度：$O(nlogM)$，其中$M$为元素的数据范围为$2^{32}$
  • 空间复杂度：$O(1)$