給定一個(gè)非空整數(shù)數(shù)組,除了某個(gè)元素只出現(xiàn)一次以外嫌吠,其余每個(gè)元素均出現(xiàn)三次止潘。找出那個(gè)只出現(xiàn)了一次的元素。
說明:
你的算法應(yīng)該具有線性時(shí)間復(fù)雜度辫诅。 你可以不使用額外空間來實(shí)現(xiàn)嗎凭戴?
示例 1:
輸入: [2,2,3,2]
輸出: 3
示例 2:
輸入: [0,1,0,1,0,1,99]
輸出: 99
思路一
1.新建列表a=[],遍歷原列表
2.原列表元素不在新列表中,則將這個(gè)元素放進(jìn)新列表中
3.若新列表中存在原列表元素炕矮,則刪除新列表中的這個(gè)元素
4.返回新列表中的元素 a=[0]
class Solution:
def singleNumber(self, nums: List[int]) -> int:
a = []
for i in nums:
if i not in a:
a.append(i)
else:
a.remove(i)
return a[0]
思路二
count()方法直接找到該元素
class Solution:
def singleNumber(self, nums: List[int]) -> int:
for i in nums:
if nums.count(i) ==1:
return i
思路三
利用set()創(chuàng)造一個(gè)無序不重復(fù)的元素集么夫,然后利用原數(shù)組所有元素的和比新的元素集的三倍少兩個(gè)一樣的數(shù)的原理
class Solution:
def singleNumber(self, nums: List[int]) -> int:
sum1 = 0
for i in nums:
sum1 += i
new_nums = set(nums)
sum2 = 0
for i in new_nums:
sum2 += i
return int((sum2*3-sum1)/2)
思路四
使用python的異或操作,0異或任何數(shù)不變肤视,任何數(shù)與自己異或?yàn)?魏割。a⊕b⊕a=b。異或滿足加法結(jié)合律和交換律钢颂。(俺也是看其他大佬的答案才知道還有這東西)這是各位大佬需要的資料
class Solution:
def singleNumber(self, nums: List[int]) -> int:
a=0
b=0
for i in nums:
a=a^i&(~b)
b=b^i&(~a)
return a
順便求個(gè)贊,闊以不拜银,各位大佬??殊鞭!