137. 只出现一次的数字 II

迈不过友情╰ 2023-02-14 10:23 72阅读 0赞

# 题目： #

[137. 只出现一次的数字 II][137. _ II]  
[面试题56 - II. 数组中数字出现的次数 II][56 - II. _ II]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解：位运算 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]

public static int singleNumber(int[] nums) { 
        int a = 0;
        int b = 0;
        for(int i = 0; i < nums.length; i++)
        { 
            a = (a ^ nums[i]) & ~b;
            b = (b ^ nums[i]) & ~a;
        }
        return a;
    }

解释一下：假设有一个数为 x，那么则有如下规律：

常用：
    x ^ 0 = x；
    
    x ^ x = 0；
    
    x & ~x = 0；
    
    x & ~0 = x；
    
    附：
    x ^ 1 = ~x；
    
    x & 0 = 0；
    
    x & 1 = x；

那么就是很好解释上面的代码了。一开始 a = 0，b = 0；代码中的 nums\[i\] 即为 x。

1. x第一次出现后，a = (a ^ x) & ~b的结果为 a = x，
    b = (b ^ x) & ~a的结果为b = 0。（因为此时a = x了）
    
    2. x第二次出现：a = (a ^ x) & ~b，a = (x ^ x) & ~0，a = 0; 
    b = (b ^ x) & ~a 化简，b = (0 ^ x) & ~0，b = x；
    
    3. x第三次出现：a = (a ^ x) & ~b， a = (0 ^ x) & ~x，a = 0; 
    b = (b ^ x) & ~a 化简， b = (x ^ x) & ~0，b = 0；
    
    所以出现三次同一个数，a和b最终都变回了0.
    
    只出现一次的数，按照上面x第一次出现的规律可知a = x, b = 0；因此最后返回a即可。

# 代码：位运算 #

public class code137 { 
    
        public static int singleNumber(int[] nums) { 
            int a = 0;
            int b = 0;
            for(int i = 0; i < nums.length; i++)
            { 
                a = (a ^ nums[i]) & ~b;
                b = (b ^ nums[i]) & ~a;
            }
            return a;
        }
        
        public static void main(String[] args) { 
            int nums[] = {  0,1,0,1,0,1,99 };
            int res = singleNumber(nums);
            System.out.println(res);
        }
    }

# 参考： #

1.  [只出现一次的数字 II][II]
2.  [137. 只出现一次的数字 II（有限状态自动机 + 位运算，清晰图解）][137. _ II_ _]
3.  [【自动机+位运算】最详细的推导过程，没有之一][Link 1]
4.  [只出现一次的数字(位运算，可以推广到在多个重复n次的数字中找到出现一次的数字)][n]
5.  [利用卡诺图生成状态转移公式，（内含对几个普遍的解法的详细解释）][Link 2]
6.  [详细通俗的思路分析，多解法][Link 3]
7.  [面试题56 - II. 数组中数字出现的次数 II（位运算 + 有限状态自动机，清晰图解）][56 - II. _ II_ _]

[137. _ II]: https://leetcode-cn.com/problems/single-number-ii/
[56 - II. _ II]: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200602113735813.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200602115341517.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[II]: https://leetcode-cn.com/problems/single-number-ii/solution/zhi-chu-xian-yi-ci-de-shu-zi-ii-by-leetcode/
[137. _ II_ _]: https://leetcode-cn.com/problems/single-number-ii/solution/single-number-ii-mo-ni-san-jin-zhi-fa-by-jin407891/
[Link 1]: https://leetcode-cn.com/problems/single-number-ii/solution/zi-dong-ji-wei-yun-suan-zui-xiang-xi-de-tui-dao-gu/
[n]: https://leetcode-cn.com/problems/single-number-ii/solution/zhi-chu-xian-yi-ci-de-shu-zi-wei-yun-suan-ke-yi-tu/
[Link 2]: https://leetcode-cn.com/problems/single-number-ii/solution/li-yong-qia-nuo-tu-sheng-cheng-zhuang-tai-zhuan-yi/
[Link 3]: https://leetcode-cn.com/problems/single-number-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--31/
[56 - II. _ II_ _]: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/mian-shi-ti-56-ii-shu-zu-zhong-shu-zi-chu-xian-d-4/