一、題目要求
二、題目背景
位運算：或，異或，與，移位
三、解題思路
（1）要求演算法時間復雜度是線性的，O(n)，想到的是先將串列排序，排序后相同的數值兩兩之間前后相鄰，進行偶數次回圈，判斷兩兩數值是否相等即可，需要注意的是考慮串列只有 一個數字和最后一個是single number的情況，
運行結果見下，時間復雜度不高，但是很占記憶體，
class Solution:
def singleNumber(self, nums: List[int]) -> int:
nums.sort()
if len(nums)==1:
return nums[-1]
else:
for i in range(0,len(nums)-2,2):
if nums[i]-nums[i+1]!=0:
return nums[i]
if i==len(nums)-3 :
return nums[-1]
（2）這道題屬于位運算操作，所以采用異或操作其實更簡便
知識點：0^a=a; b^a^a=b
或：只要有1就得1
與：只要有0就得0
異或：只要相等就得0
位移動:
從運行結果來看，還是很耗記憶體，執行時間也比上面的慢一點，主要是異或操作回圈了串列中所有值
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/135933.html
標籤：其他
上一篇：靜態創建二叉樹及其遍歷