題目描述

數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。

你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。

1 <= 數(shù)組長度 <= 50000

題目樣例

示例

輸入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 輸出: 2

題目思考

1. 如何不使用額外空間?
2. 如果題目不保證一定存在多數(shù)元素又該怎么辦?

解決方案

思路

• 一個最簡單的思路是用一個計數(shù)字典存每個數(shù)字的出現(xiàn)次數(shù), 找最大的那個即可, 但這需要額外的空間, 不是面試官心目中的理想答案
• 重新分析題目, 某個數(shù)字出現(xiàn)超過一半, 那意味著其他數(shù)字的數(shù)目之和都小于它, 如果我們將這些 不同數(shù)字進(jìn)行兩兩抵消, 那么最后剩余的那個數(shù)字一定是超過一半的那個數(shù)字, 這就引出了下面的思路:
1. 維護(hù)一個當(dāng)前候選者, 以及當(dāng)前它的計數(shù), 初始化就是數(shù)組頭一個數(shù)字, 計數(shù)為 1
2. 從第二個數(shù)字開始遍歷數(shù)組, 如果當(dāng)前數(shù)字等于候選者, 那么計數(shù)值加 1, 否則就減 1 表示抵消了一個數(shù)字
3. 如果此時計數(shù)小于 0 的話, 就說明之前的候選者這個時候要被淘汰了, 因為它已經(jīng)被抵消光了. 所以就重新選擇當(dāng)前的數(shù)字作為新的候選者, 同時重置計數(shù)值為 1.
4. 這樣最后剩余的那個候選者一定是最終結(jié)果, 因為此題的前提是一定存在這樣的數(shù)字
• 當(dāng)然, 如果題目不保證一定存在多數(shù)元素, 那么我們在得到最終候選者之后, 需要重新遍歷一遍數(shù)組并累加其計數(shù), 確保其計數(shù)超過一半, 不然的話就說明整個數(shù)組沒有多數(shù)元素. 例如數(shù)組 [1,2,3], 利用此方法得到的最終候選者為 3, 但它并不是多數(shù)元素, 只是恰好最后一個被選出來的候選者而已.

復(fù)雜度

• 時間復(fù)雜度 O(N)
• 只需要遍歷數(shù)組一遍
• 空間復(fù)雜度 O(1)
• 只使用了幾個變量

代碼

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # 初始化候選者和計數(shù)
        res = nums[0]
        cnt = 1
        for x in nums[1:]:
            if x == res:
                # 當(dāng)前元素等于候選者, 計數(shù)值+1
                cnt += 1
            else:
                # 否則計數(shù)值-1
                cnt -= 1
                if cnt < 0:
                    # 如果計數(shù)值小于0的話, 就說明之前保存的候選者現(xiàn)在被淘汰了, 將當(dāng)前元素變?yōu)樾碌暮蜻x者, 并重置計數(shù)值為1
                    res = x
                    cnt = 1
        return res