LeetCode 136. Single Number
每日題。連續兩天都是簡單題,真稀奇。
題目
輸入一個不為空的陣列整數nums,裡面除了只有一個數只出現一次外,其他都出現兩次,求只出現一次的數是多少。
你必須使用空間O(1)的演算法。
解法
既然都說只能用常數空間,那就是指定XOR運算了。
XOR有個特性,對同樣的數字做兩次運算會抵消,因此把整個nums的數相互做XOR就可以得到答案。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
x = 0
for n in nums:
x ^= n
return x
寫成pythonic的風格。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return reduce(operator.xor, nums)