从一组数字中找出只出现一次的数字

less than 1 minute read

最近被人问到了一个算法问题,题目是这样的
一组数字中只有一个数字出现了一次。其他所有数字都是成对出现的。 请找出这个数字

举例:
如果这组数字为[1, 3, 5, 1, 3, 5, 7], 那么7就是我们要找的结果

根据楼主上学的时候的经验, 与数字有关的问题首选异或这种位运算, 本例利用的是异或相同为0 ,不同为1的特性。具体到这个题目上如果某个数字成對出现,例如1,1, 那么这一对数字的异或的结果就是所有的位都是0, 唯独单独出现的那个数字没有数字与他异或, 这个数为1的位的值将得到保留。

综上,我们把这组数据做异或运算1^3^5^1^3^5^7, 得到的最后的结果为7, 而7就是我们要找的数字

复杂度分析: 时间复杂度O(n), 空间复杂度O(n)

延伸问题, 如果把只有一个数字不同改为有2个数字只出现一次, 如果找出这2个数

这里假设这组数字为[1,3,5,7,1,3,5,9]

顺着上面的思路,我们先把上面的一组数做异或运算, 结果为1110(十进制为14), 所得到的这个结果其本质就是那两个单独出现的数的亦或结果(7[0111]和9[1001]),由于亦或其本质就是相同为0,相异为1,所以这个数每个为1的位就是其不同的位,我们可以随机找出它第一个为1的位进行标记,然后把这组数字分为2组,这样没一组就只有一个数是单独出现的,剩下的就是套用上面的方法找出这个数字

二进制 十进制
0001 1
0011 3
0101 5
0111 7
1001 9

这里我们就采用第一位对上面的数字进行分组, 分组结果为[1,3,5,7,1,3,5]和[9], 因为只有9的第一位为1, 因此这次分组9被单独分到了一组,如果采用第二为来分组,其结果为[1,3,1,3,9], [5,5,7], 随便一直分组方式都是可以的。

接下来对没一组数字进行异或, 得到7和9两个数字,就算我们要找的数字