一个有N个数的数组里, 每个数字都出现两次, 现在取出一个数, 根据剩下的数字, 猜测取出的数的值(要求时间复杂度为N, 空间复杂度为1)
异或运算
- 两个相同的数进行异或运算, 结果为0
5^5 == 0 - 0 与非零数进行异或运算, 结果为非零数本身
0^10 == 10 - 异或运算符合交换律
10^20^30^40 == 20^30^10^40
解题思路:
解题图示
代码实现:
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result = nums[0]
for num in nums[1:]:
result ^= num
return result
def main():
so = Solution()
result = so.singleNumber([10, 20, 50, 80, 10, 50, 80, 5, 20])
print("单身数为:", result)
if __name__ == '__main__':
main()
