【解题报告】lintcode82落单的数

题意

数组里所有数都出现了两次,但是其中有一个只出现了一次,找出它
时间复杂度O(n)

解答

使用位运算,异或运算
由于其结合律
结合律:A^(B^C)=(A^B)^C
且如果两个数字相同,异或结果为0,0与仍和数字的异或为这个数字本身
我们把所有数字异或起来,就是我们要找的结果了

代码

u3coding
A software developer

Leave a Comment

Your email address will not be published. Required fields are marked *

*