LeetCode如何找出只出現(xiàn)一次的數(shù)字

這篇文章主要為大家展示了“LeetCode如何找出只出現(xiàn)一次的數(shù)字”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“LeetCode如何找出只出現(xiàn)一次的數(shù)字”這篇文章吧。

給定一個(gè)非空整數(shù)數(shù)組，只有一個(gè)數(shù)字出現(xiàn)一次，其余出現(xiàn)三次，找出只出現(xiàn)一次的數(shù)字。如輸入[3,4,5,4,3,3]，輸出5。

對(duì)集合進(jìn)行切片，生成三個(gè)集合，找到與另外兩個(gè)集合不同的集合缺少的數(shù)字。如集合[2,2,3,2]，先對(duì)集合進(jìn)行排序，得到[2,2,2,3]，通過(guò)切片生成集合[2,3]、[2]、[2]，比較集合之間元素差別，得到輸出結(jié)果3。

class Solution:    def singleNumber(self, nums: List[int]) -> int:        nums.sort()         a=len(set(nums[::2]))        b=len(set(nums[1::2]))        if a==b:            return list(set(nums[::3]) - set(nums[2::3]))[0]        else:            return list(set(nums[::3]) - set(nums[1::3]))[0]

通過(guò)set方法時(shí)空復(fù)雜度都是O(N)，位運(yùn)算可以使得空間復(fù)雜度降為O(1)。在LeetCode刷題DAY 5：只出現(xiàn)一次的數(shù)字中使用的“異或”其實(shí)就是同一狀態(tài)出現(xiàn)兩次則歸零，即0->1->10=0的變化，在本題中則是要讓同一狀態(tài)出現(xiàn)三次歸零，即00->01->10->11=00，可見(jiàn)這里需要用兩個(gè)bit進(jìn)行狀態(tài)記錄。

這里需要注意的是，要對(duì)two、one兩位分別計(jì)算。對(duì)于one，當(dāng)two=1時(shí)，不管輸入是什么下一步的one都為0，當(dāng)two=0時(shí)，輸入1則one=～one，輸入0則one不變。對(duì)于two，依賴于one變化后的狀態(tài)，one新?tīng)顟B(tài)為1時(shí)，two則為0，one新?tīng)顟B(tài)為0時(shí)，輸入1則two=～two，輸入0則不變。因?yàn)槌霈F(xiàn)三次就歸零，所以one最后保留的是只出現(xiàn)了一次的值。

class Solution:    def singleNumber(self, nums: List[int]) -> int:        one,two = 0,0        for i in nums:            one = one^i & ~two            two = two^i & ~one        return one

以上是“LeetCode如何找出只出現(xiàn)一次的數(shù)字”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！