這篇文章將為大家詳細(xì)講解有關(guān)LeetCode如何計(jì)算數(shù)組中數(shù)字出現(xiàn)的次數(shù)，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。
從網(wǎng)站建設(shè)到定制行業(yè)解決方案，為提供網(wǎng)站設(shè)計(jì)制作、網(wǎng)站制作服務(wù)體系，各種行業(yè)企業(yè)客戶提供網(wǎng)站建設(shè)解決方案，助力業(yè)務(wù)快速發(fā)展。創(chuàng)新互聯(lián)將不斷加快創(chuàng)新步伐，提供優(yōu)質(zhì)的建站服務(wù)。
一個(gè)整型數(shù)組 nums 里除兩個(gè)數(shù)字之外，其他數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。要求時(shí)間復(fù)雜度是 O(n)，空間復(fù)雜度是 O(1)。
輸入：nums = [4,1,4,6]
輸出：[1,6] 或 [6,1]
輸入：nums = [1,2,10,4,1,4,3,3]
輸出：[2,10] 或 [10,2]
重慶分公司
重慶分公司
xor & -xor, 直接就能求得最低位的 1 對(duì)應(yīng)的數(shù)字, 這個(gè)大家手動(dòng)模擬下補(bǔ)碼就知道是為什么了class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
# 先拿到所有數(shù)字的異或結(jié)果, 該結(jié)果一定至少有一位是1, 否則就不可能有兩個(gè)出現(xiàn)一次的數(shù)字
xor = 0
for n in nums:
xor ^= n
# 然后隨便針對(duì)異或結(jié)果的某一位1, 將原數(shù)組分為兩類, 自然兩個(gè)出現(xiàn)一次的數(shù)字就會(huì)分別落在不同類里面, 否則其異或結(jié)果的這一位不可能是1
# 這里直接利用樹狀數(shù)組的lowbit(即原來的數(shù)字的最低位的1)
mask = xor & -xor
a, b = 0, 0
for n in nums:
if n & mask:
# 如果數(shù)字的這一位是1, 歸為一類, 求它們的異或值, 即為其中一個(gè)出現(xiàn)一次的數(shù)
a ^= n
else:
# 如果數(shù)字的這一位是0, 歸為另一類, 求它們的異或值, 即為另一個(gè)出現(xiàn)一次的數(shù)
b ^= n
return [a, b]
關(guān)于“LeetCode如何計(jì)算數(shù)組中數(shù)字出現(xiàn)的次數(shù)”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請把它分享出去讓更多的人看到。
