审题:
数组中除了答案元素只出现一次外,其他元素都会出现三次,我们需要找到并返回答案元素
思路:
由于现在会出现三次,所以利用异或运算符的方法就会失效。而所有数据都在32位二进制范围内,所以我们采用依次确定二进制位的方法来计算
方法:依次确定二进制位
对于只出现一次的数据,它的第i位二进制数可能是0或1.
对于出现三次的数据,它的第i位二进制数据可能是0/1,但是若将他们加起来就一定是3的倍数(0或3)
而如果我们对数组中所有元素第i位二进制数的和除以3并取余数就可得到答案第i位的二进制数,然后将这位给到答案上即可
解题:
外层循环:目的是进行答案不同位数的计算与赋值
内层循环:将nums数组所有元素的第i位(i从0开始)加起来给到total
if语句:当余数是1说明我们答案在当前位数的二进制数是1,需要把1给到答案的第i位
若余数不是1,说明我们答案在当前位数的二进制数是0,由于我们答案初始化为0(相当于32为二进制数都是0),所以0就不用我们去赋值了
关键代码:
1.如何得出第i位二进制数的值?
首先把数据右移i位,然后利用位与运算和1进行运算
因为1的前面31位都是0,所以不管e前面31位是多少,最后都会变成0。也就是需要比较的只有第32位,我们把第i位都移动到32位,如果该位大小为1,那么和1进行位与操作就可以得出结果为1,否则为0.这样就实能将对应位大小提取出来
2.如何将答案的第i位赋值为1?
首先把1左移i位,然后与答案进行位或运算
因为1左移i位后,其他位数都为0,位或操作的性质决定了我们不会改变答案的其他位的值。
此时因为答案第i位是0,而我们左移后的“1”的第i位是1了,根据位或性质,第i位运算出来就是1,又因为其他位不变,所以成功在答案其他位不变的情况下实现了赋值1
补充:
位与运算符:&
当两个二进制数对应位的值都是1,那么运算得出1,否则为0
eg:0011 & 1100 -》0000
位或运算符:|
当两个二进制数对应位的值有一个是1,那么就得出1,否则为0
eg:0011 & 1100 ——》1111
137. 只出现一次的数字 II - 力扣(LeetCode)