初級演算法篇之數組 <5>

來自專欄 Python異世界的刷題之路

題目:136.只出現一次的數字

給定一個非空整數數組，除了某個元素只出現一次以外，其餘每個元素均出現兩次。找出那個只出現了一次的元素,演算法應該具有線性時間複雜度，不使用額外空間來實現

測試示例:

示例 1:輸入: [2,2,1]輸出: 1示例 2:輸入: [4,1,2,1,2]輸出: 4

解題開始:

#1.分析題目:

1.數組是全為整型，且為非空。2.只有一個元素出現一次，其他的元素都出現過兩次。3.演算法要滿足線性時間複雜度，也就是 (n)。4.不能使用額外空間。

#2.思路:

#咱們可以使用異或的知識來進行解題。#異或的特性如下：1 ^ 2 ^ 1 = 2 0 ^ 3 = 3 0 ^ 3 ^ 3 = 0也就是說，異或，如果是有兩個相同的，值是會抵消的。 異或的結果就是只出現一次的元素值。

#3代碼的實現

class Solution: def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ ret = 0 for i in nums: ret ^= i return ret

推薦閱讀：