Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
普通解刚看到的这个题目第一时间想到的就是a[i]++,最后找出a[i]==1的方法,但一方面python的数组操作没有那么灵活,再就是负数部分不好处理,想了一会儿比较好的方法应该是有一个容器,第一次遇到该值时将其放进去,第二次遇到时就将该值取出,这样整个输入结束后容器中就只剩下我们要的single number了,时间复杂度也只是O(n),列表在不知道索引的情况下不方便移除指定数据,而set中的remove方法则刚好适合,所以最终代码如下:
class Solution: def singleNumber(self, nums: List[int]) -> int: single = set() for num in nums: if num in single: single.remove(num) else: single.add(num) for num in single: return num 不使用额外空间的解提示里面提醒我们能不能不使用额外的内存就实现它,在不增加时间的情况下百思不得其解,后来看到了讨论区大神的解答才知道可以用异或的方法来做,也更新了我对异或的理解(原本以为异或只适用于0和1)。首先介绍下异或,异或操作最基本的就是
0 XOR n = n n XOR n = 0同时异或还具有一大特点就是其可交换性,即
a xor b xor c 三者可以任意交换结果不变所以将所有输入的值异或再交换,即可得到single number,代码如下
class Solution: def singleNumber(self, nums: List[int]) -> int: xor = 0 for i in range(len(nums)): xor ^= nums[i] return xor