您好,登錄后才能下訂單哦!
這篇文章主要為大家展示了“LeetCode如何找出數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字”,內(nèi)容簡(jiǎn)而易懂,條理清晰,希望能夠幫助大家解決疑惑,下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“LeetCode如何找出數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字”這篇文章吧。
數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半,請(qǐng)找出這個(gè)數(shù)字。
你可以假設(shè)數(shù)組是非空的,并且給定的數(shù)組總是存在多數(shù)元素。
1 <= 數(shù)組長(zhǎng)度 <= 50000
輸入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 輸出: 2
[1,2,3]
, 利用此方法得到的最終候選者為 3, 但它并不是多數(shù)元素, 只是恰好最后一個(gè)被選出來(lái)的候選者而已.O(N)
O(1)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
# 初始化候選者和計(jì)數(shù)
res = nums[0]
cnt = 1
for x in nums[1:]:
if x == res:
# 當(dāng)前元素等于候選者, 計(jì)數(shù)值+1
cnt += 1
else:
# 否則計(jì)數(shù)值-1
cnt -= 1
if cnt < 0:
# 如果計(jì)數(shù)值小于0的話, 就說(shuō)明之前保存的候選者現(xiàn)在被淘汰了, 將當(dāng)前元素變?yōu)樾碌暮蜻x者, 并重置計(jì)數(shù)值為1
res = x
cnt = 1
return res
以上是“LeetCode如何找出數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對(duì)大家有所幫助,如果還想學(xué)習(xí)更多知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。