leetcode with python:136. Single Number

题目:

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

给定一个阵列,里面除了一个数以外其余都两两相对,找出那单独的数
ex:input:[4,1,2,1,2]=>output:4

一开始我的想法是遍历然后用set纪录

class Solution:    def singleNumber(self, nums: List[int]) -> int:        s=set()        for i in nums:            if i in s:                s.remove(i)            else:                s.add(i)         return s.pop()

建立一个set,遍历阵列的过程若值不在set内就加入set,在set内就将其移出set
因为除我们要的数以外都是两两相对
最后留在set的数便是我们要的single number
最后执行时间128ms(faster than 99.02%)

但我后来发现其实这样解不是正规的
因为题目有规定解法的时间複杂度要O(n)且空间複杂度要O(1)
而上述的解虽然时间複杂度是O(n),但由于开了set纪录所以空间複杂度来到O(n)
所以这个解法是不被接受的虽然会过

要找出不开新空间的解法,我百思不得其解
虽然在related topic中看到了位元运算(Bit Manipulations)
即以位元组为处理对象下去操作
但我仍不知道如何运用
最后看讨论区才知道要用XOR(^)这个我从未见识过的运算子下去运算

class Solution:    def singleNumber(self, nums: List[int]) -> int:        ans=0        for n in nums:            ans=ans^n        return ans

XOR,即^,是对二进位型态的两数的每一位进行比较
若该位两数相同(1对1,0对0)则回传0,两数不同(1对0)则回传1
因此两个相同的数进行^运算会回传0,因为两数二进位每一位都相同
而一数和0进行^运算会回传该数,因为每个1遇到0都会回传1,每个0遇到0都会回传0
我们利用这两个性质就能迅速解开这题
因为两两一对的数终会化成0
0再跟single number进行^运算得到一样的值
所以只要从第一项开始跟每一项行^运算最后就能得到single number(^适用交换律和结合律)
最后执行时间119ms(faster than 99.93%)

这是第二次在leetcode写不出题目要求的解答
不过是自己完全不认识的语法让挫折感没那么深
学起来以后遇到就会用了ouob

本题学习到的重点:位元运算(Bit Manipulations)之XOR
那我们下题见