LeetCode_260 只出现一次的数字 III(Java版)

解题思路

通过位运算进行筛选
第一次遍历,全体异或结果为xorsum
取出两个元素不同的地方lsb = xorsum & (-xorsum)为特殊位
第二次遍历,直接分成两组,一组特殊位是1,另一组特殊位是0,分组进行异或运算,两两相等得0,结果就是单独元素,保存到数组

代码

异或^= 0^0=0; 0^1=1; 1^0=1; 1^1=0;
所有数据进行异或,两两成对抵消变成0,最后只有两个元素不同,必定不为0
两两相同的元素,异或为0,最后实际比较的就是两个不同的元素

int xorsum = 0;
for (int num : nums) {
    xorsum ^= num;
}

取出二进制,倒数最后一个不是0的位置

与运算& 0^0=0; 0^1=0; 1^0=0; 1^1=1;【只有都为1,才是1】
原码xorsum
补码(-xorsum)
反码是原码取反得到,1变0,0变1 【所以如果 原码&反码,结果必定是0】
补码是反码+1得到,原本两两相反,现在+1后,如果原本是0,不论怎么变与运算&后,肯定还是0,
倒数第一个xxx1000,后边反码xxx0111,加一后就肯定是xxx1000,与运算&直接找到倒数第四位是1

LeetCode_260 只出现一次的数字 III(Java版)

int lsb = xorsum & (-xorsum);//找1的地方,就是两个数不同的地方

【其中一个数的这个位置是1,另一个数的这个位置是0】
将问题化为找到这个位置是1的数,和这个位置是0的数
直接遍历一边,将这个位置是1的全部分出来,进行异或运算,最后两两成对变成0,只有单独的那一个不同的留下;
同理,将位置上是0的,分出来,进行异或运算,最后仍是两两成对变成0,只有单独的那个一个不同的得以保存;

int[] result = new int[2];
for (int num : nums) {
    if ((num & lsb) == 0) {
        result[0] ^= num;
    } else {
        result[1] ^= num;
    }
}
return result;
上一篇:数与矩阵相乘


下一篇:260. 只出现一次的数字 III