跳转到内容

数组中只有一个数出现一次,其余都出现两次,怎样用异或找出来?

把所有数依次异或即可。异或满足交换律、结合律,且 a ^ a = 0、a ^ 0 = a。成对的数会抵消,留下唯一出现一次的数,与输入顺序无关。

def single_number(nums):
result = 0
for value in nums:
result ^= value
return result

例如,[4, 1, 2, 1, 2] 可以按运算规律看成 4 ^ (1 ^ 1) ^ (2 ^ 2),结果是 4。对于机器字长内的整数,时间 O(n),额外空间 O(1)。

这依赖“非空数组、一个数出现一次、其余每个数恰好出现两次”的前提,算法本身不验证它们。若有两个数只出现一次,结果只是这两个数的异或;若其余数出现三次,也不能照搬。原帖只写“找只出现一次的数字”,面试时应先确认次数条件。

资料

LeetCode 136 的完整次数约束。题目中的成对条件按标准算法题补明,不声称原帖公开了全部约束。