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