題目描述

數(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. 如果題目不保證一定存在多數(shù)元素又該怎么辦?

解決方案

思路

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

復(fù)雜度

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

代碼

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