「只出現一次的數字」leetcode刷題|007

題目

給定一個非空整數數組，除了某個元素只出現一次以外，其餘每個元素均出現了三次。找出那個只出現了一次的元素。

說明：

你的演算法應該具有線性時間複雜度。 你可以不使用額外空間來實現嗎？

示例 1:

輸入: [2,2,3,2]

輸出: 3

示例 2:

輸入: [0,1,0,1,0,1,99]

輸出: 99

解答

這道題是中等難度的題目，剛開始我一看，哎，這麼簡單，順手就寫了起來

class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ for i in nums: if nums.count(i) == 1: return i

運行一看也正確，沒啥問題，統計數字嘛，以前也遇見過。

看一下我的運行結果

可以看到只打敗了10%的提交者，雖然解決了問題，可耗時太長，顯然不是這道題的最好解決方法。

看看大佬的代碼

class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) == 1: return nums[0] a = sorted(nums) for i in range(0,len(nums)-1): if a[i] == a[i-1] or a[i] == a[i+1]: continue else: return a[i] return a[-1]

之所以我的代碼耗時時間長，是因為每次統計都要遍歷一遍列表，大佬的代碼只遍歷了一次。

再看一個

class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ buffer_dict = {x: 0 for x in nums} for x in nums: buffer_dict[x] += 1 for x in buffer_dict.items(): if x[1] == 1: return x[0]

利用字典來做，時間複雜度最小，耗時28ms,目前來說最好的解決方法。