🌕🌕 137. 只出现一次的数字 II

难度: 🌕🌕

问题描述

---

解法

class Solution {
    public int singleNumber(int[] nums) {
        // 思路：
        // 位运算
        // 可以看出，将 nums 的每一位拆分来看，设其中一位为 i
        // 那么 当 i == 1 时，满足状态转换关系为 0 -> 1 -> 2 -> 0 -> ...
        // 当 i == 0 时，当前值不变
        // 可以用 2 位表示 [0, 2] 这 3 种状态，真值表如下：
        // high low     i  |    high' low'
        // 0    0       0  |    0     0
        // 0    1       0  |    0     1
        // 1    0       0  |    1     0
        // 0    0       1  |    0     1
        // 0    1       1  |    1     0
        // 1    0       1  |    0     0
        int high = 0;
        int low = 0;
        for(int i : nums) {
            int tmp1 = (high & (~low) & (~i)) | ((~high) & low & i);
            int tmp2 = ((~high) & low & (~i)) | ((~high) & (~low) & i);
            high = tmp1;
            low = tmp2;
        }
        // 由于仅有一个元素出现一次，说明 high 必不可能出现 1 的情况，因此只有 00 & 01 2 种可能情况，因此只需要返回低位值
        return low;
    }
}

---

输出