136-137-260-只出现一次的数字

136-只出现一次的数字

https://leetcode-cn.com/problems/single-number/

137-只出现一次的数字II

https://leetcode-cn.com/problems/single-number-ii/

260-只出现一次的数字III

https://leetcode-cn.com/problems/single-number-iii/

先看136，位运算的经典题，知乎凡是有吹位运算的回答的，没有不拿这题开刀的。

原理是a ^ b ^ b = a

public int singleNumber(int[] nums) {
    int res = nums[0];
    for(int i = 1; i < nums.length; i++){
        res ^= nums[i];
    }
    return res;
}

跳过137，先看260题，相比136题它从一个数变成了两个数，难度大了很多

思路：

我们假设只出现一次的两个数为a, b，按照136题的思路，遍历异或，得到的结果应该是res = a ^ b

res中二进制为1的位就是a和b二进制不一样的位，不管哪个1，我们可以将这个位为1的所有数和这个位为0的所有数分开，那么就可以得到两组数

a, c, c

b, d, d

又成为了136题的情况

public int[] singleNumber(int[] nums) {
    int[] res = new int[2];
    int orRes = nums[0];	//orRes = a ^ b
    for (int i = 1; i < nums.length; i++) {
        orRes ^= nums[i];
    }

    int lowBit1 = findLow1(orRes);

    //用lowBit1这一位分成两组，分别进行异或，和136题一样
    for (int i = 0; i < nums.length; i++) {
        if ((nums[i] >> lowBit1 & 1) == 1){
            res[0] ^= nums[i];
        }else {
            res[1] ^= nums[i];
        }
    }
    return res;
}

//找一位1，哪一位都行，我这里取得是最低位，方便
public int findLow1(int num){
    int i = 0;
    while (num != 0 && (num & 1) != 1){
        num = num >> 1;
        i++;
    }
    return i;
}

137题

这题放到最后讲是因为说实话比较难，难在前面的是其他元素出现两次，而“异或”这个位运算刚好使得b^b=0。这题难在出现了3次，意味着我们需要设计一个“运算”，使得b★b★b=0

评论区的代码大多是这样的，却没解释清楚

public int singleNumber(int[] nums) {
    int a = 0, b = 0;
    for (int x : nums) {
        a = (a ^ x) & ~b;
        b = (b ^ x) & ~a;
    }
    return a;
}

我认为解释的最好的是题解的这一篇

https://leetcode-cn.com/problems/single-number-ii/solution/luo-ji-dian-lu-jiao-du-xiang-xi-fen-xi-gai-ti-si-l/

简单解释就是3种状态需要两位，所以从00，01，10，11四个中任选3个，比如00，01，10，那么需要画真值表使其满足00->01, 01->10, 10->00

Z是什么，Z为1代表这个数出现了，那么

一开始为00，Z第一次出现00->01，第二次出现01->10，第三次出现10->00

那么就可以写表达式了，根据数电的知识，写x_new只看x_new为1的

事实上，我认为到这一步就够了，化简什么的一时半会写不出来，那么我们就以这个为例，写的时候要注意，不要直接变x而是用x_new存起来，否则计算y_new时改变了x的值。当然，python可以a, b = b, a另说

public int singleNumber(int[] nums) {
    int x = 0, y = 0;
    for (int z : nums) {
        int x_new = (x & ~y & ~z) | (~x & y & z);
        int y_new = (~x & ~y & z) | (~x & y & ~z);
        x = x_new; y = y_new;
    }
    return y;
}