找出偶数次中只出现一次的数

March 07, 2019

又一个群论的精彩应用:

LeetCode 第 136 题 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

计算机中整数是用二进制位序列表示的,在异或运算 (XOR) 下(等长的,如 3232 位)二进制序列构成一个 Abel 群,单位元是 00,逆元是本身。

32 位序列一一对应着 {1,2,...,32}\{1,2,...,32\} 集合的子集,而异或运算对应着集合的对称差运算,这个群和 K 连续位的最小翻转次数:群论解释 中所构造的群是同构的。

使用交换律、结合律,以及逆元为本身的性质:

aba=aab=(aa)b=ba \circ b \circ a = a \circ a \circ b = (a \circ a) \circ b = b

因此对整数列表从单位元 00 开始不断进行异或运算,最终的值就是那个只出现了一次的元素。

(PS:题目改为“其他的数出现了偶数次(22, 44, 66...等),只有一个数出现了 11 次”,更能体现此种解法的妙处