資訊專欄INFORMATION COLUMN
摘要：描述給定一個整數(shù)數(shù)組，除了某個元素外其余元素均出現(xiàn)兩次。請找出這個只出現(xiàn)一次的元素。備注你的算法應(yīng)該是一個線性時間復(fù)雜度。
描述：
給定一個整數(shù)數(shù)組，除了某個元素外其余元素均出現(xiàn)兩次。請找出這個只出現(xiàn)一次的元素。
備注：
你的算法應(yīng)該是一個線性時間復(fù)雜度。 你可以不用額外空間來實現(xiàn)它嗎？
實現(xiàn)：#我的實現(xiàn)方法:利用count找出元素的個數(shù)，如果個數(shù)為1的就是要找的
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in nums:
n = nums.count(i)
if n ==1:
return i
但是這個方法的時間超時了，達不到題目的性能要求
可以利用Counter,可以將list轉(zhuǎn)化成，list里面的value對應(yīng)個數(shù)的字典
例如：numss = [2,2,1,1,1,3]
{1: 3, 2: 2, 3: 1}
from collections import Counter
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dict_nums = dict(Counter(nums))
nums_list = dict_nums.keys()
for i in nums_list:
if dict_nums[i]==1:
return i
樓下回復(fù)大神提示說可以先對list進行排序：想到一種方法：排序之后進行比較：
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
if len(nums)==1:
return nums[0]
else:
if nums[0] != nums[1]:
return nums[0]
elif nums[len(nums) - 1] != nums[len(nums) - 2]:
return nums[len(nums) - 1]
else:
for n in range(len(nums)):
if nums[n + 2] != nums[n + 1] and nums[n+2] != nums[n+3]:
return nums[n + 2]
根據(jù)大牛提示的每個元素異或的方式：
由于A XOR A = 0 且 ((A^A) ^ (B^B) ^ (C^C) ^ (D^D) ^ E) = ((0^ 0 ^ 0 ^ 0 ^ E) =E
直接把整個數(shù)組異或運算，最后的出來的就是只出現(xiàn)一次的數(shù)字了。
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ss = 0
for i in nums:
ss = ss^i
return ss
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/41481.html
摘要：解決方案異或操作異或運算是對于二進制數(shù)字而言的，比如說一個有兩個二進制，如果兩個值不相同，則異或結(jié)果為。比如說，本質(zhì)上其實是和的每一對比特位執(zhí)行異或操作，等價于下面數(shù)字對應(yīng)的二進制數(shù)字對應(yīng)的二進制數(shù)字對應(yīng)的二進制因此的結(jié)果就為啦。 新年第一篇文章，先祝大家新年快樂??！那么接下來進入正文。 前言 前陣子突發(fā)奇想，突然開始刷leetcode。其中刷到了一道有意思的題目，發(fā)現(xiàn)這道題是當(dāng)時秋招...
摘要：使用位運算數(shù)組只出現(xiàn)一次數(shù)字的數(shù)組得到最低的有效位，即兩個數(shù)不同的那一位看完上面的解法，我腦海中只有問號的存在，啥意思啊下面就讓我們簡單了解一下位運算并解析一下這三道題目。另，負數(shù)按補碼形式參加按位與運算。你可做過這幾道題？ 在面試的準(zhǔn)備過程中，刷算法題算是必修課，當(dāng)然我也不例外。某天，我刷到了一道神奇的題目： # 136. 只出現(xiàn)一次的數(shù)字 給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外...
摘要：簡單介紹一下位運算異或運算異或邏輯的關(guān)系是當(dāng)不同時，輸出當(dāng)相同時，輸出。另，負數(shù)按補碼形式參加按位與運算。使一個數(shù)的最低位為零，可以表示為。，截止到這兒，三道題目中使用的位運算介紹完畢，那么這里我們插入一下的詳細題解。你可做過這幾道題？ 在面試的準(zhǔn)備過程中，刷算法題算是必修課，當(dāng)然我也不例外。某天，我刷到了一道神奇的題目： # 136. 只出現(xiàn)一次的數(shù)字 給定一個非空整數(shù)數(shù)組，除了某個元素只...
摘要：題目描述給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。說明你的算法應(yīng)該具有線性時間復(fù)雜度。你可以不使用額外空間來實現(xiàn)嗎示例輸入輸出示例輸入輸出代碼描述 題目描述 給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。 說明： 你的算法應(yīng)該具有線性時間復(fù)雜度。 你可以不使用額外空間來實...
摘要：按照思路一和思路二很容易將這題解決。在這里，我們希望將出現(xiàn)三次的數(shù)字通過操作劃掉。之后，我們使用和分別來記錄第一位和第二位的情況。最后只出現(xiàn)一次的數(shù)值應(yīng)該是保存在中，換句話說，最后應(yīng)該全是。 題目要求 Given an array of integers, every element appears three times except for one, which appears e...
閱讀 2078·2023-04-25 17:48
閱讀 3590·2021-09-22 15:37
閱讀 2941·2021-09-22 15:36
閱讀 6007·2021-09-22 15:06
閱讀 1644·2019-08-30 15:53
閱讀 1431·2019-08-30 15:52
閱讀 716·2019-08-30 13:48
閱讀 1126·2019-08-30 12:44
