Single Number 普通解及最小空间解(理解异或)

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

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zywdfx.html