此题困扰我多时,即便是看了诸多结题报告之后
依然是一道位操作,是打开思路的一道题,对异或、与、非等操作加强了理解。
int singleNumber(int* nums, int numsSize){
int ones = 0;
int twos = 0;
for (int i = 0; i < numsSize; i++){
ones = ones ^ nums[i] & ~twos;
twos = twos ^ nums[i] & ~ones;
}
return ones;
}
这是一份标准答案,但是却有多种理解,我理解的版本是:
首先,数组中的元素是可以任意交换位置的,三个同样的元素,可以交换到一起(其实没关系,只是便于理解)
-
ones、twos所代表的含义:在Single Number I中,两个同样的元素可以通过异或操作消除,此题中的三个元素或者扩展到多个元素,如何消除,最终获得唯一的元素?
- ones:记录元素第一次出现
- twos:记录元素第二次出现
- 当元素第三次出现时,被消除(相当于三个数都未曾来过)
-
对公式的理解是关键:
-
ones = ones ^ nums[i] & ~twos
:第一次出现时,与nums[i]异或,记录到ones变量中,并确保不是第二次出现;ones变量为1,twos变量为0 -
twos = twos ^ nums[i] & ~ones
:第二次出现时,与nums[i]异或,记录到twos变量中,并清空第一次出现的记录;ones变量为0,twos变量为1 - 当第三次出现时,都置为0
-