LeetCode 面试经典150题 137.只出现一次的数字II

题目：

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

思路：

方法一：暴力思路

方法二：

其中 & 运算相当于为异或运算添加了一个约束：当……为 1 时，才执行异或操作。

由于位运算具有「并行计算」的特点，上述运算规则可以推广到多个比特的情况。

最后，由于模 3 加法的结果要么是 0，要么是 1，没有 2，那么根据 b 的定义，这刚好就是 b，所以最后返回 b。

代码：

class Solution {  // 方法一
    public int singleNumber(int[] nums) {
        int ans = 0;  // 返回结果
        for (int i = 0; i < 32; i++) {  // 统计32位每一位上1的个数
            int count = 0;  // 记录每一位上1的个数
            for (int num : nums) {
                count += num >> i & 1;  // 先右移然后再取最低位
            }
            ans |= count % 3 << i;  // 先模3再左移，不要忘了左移
        }
        return ans;
    }
}

class Solution {  // 方法二
    public int singleNumber(int[] nums) {
        int a = 0, b = 0;
        for (int x : nums) {
            int tmpA = a;
            a = (a ^ x) & (a | b);
            b = (b ^ x) & ~tmpA;
        }
        return b;
    }
}

性能：

方法一 时间复杂度O（32n）  空间复杂度O（1）

方法二 时间复杂度O（n）  空间复杂度O（1）

知识点：

1、Java中运算符的优先级

++ -- ~  -> 算术运算符(+-*/) -> 关系运算符(> < >= <=)  ->  逻辑运算符(& | ^) -> 条件运算符(?:) ->赋值运算符

2、模2加法、模3加法