陣列入門題 用BM投票演算法 找超過n/3的領先者 Majority Element II Leetcode #229

這題的題目在這裡:

題目敘述

題目會給定我們一個陣列，陣列長度為n。
要求我們找出裡面出現次數超過 n / 3次的數字。

測試範例

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

Input: nums = [1,2]
Output: [1,2]

約束條件

Constraints:

• 1 <= nums.length <= 5 * 104
• -109 <= nums[i] <= 109

 Follow up: Could you solve the problem in linear time and in O(1) space?

演算法

如果只是第一直覺的話，第一輪掃描先用字典來統計出現次數，第二輪再挑選出現次數超過 n/3次的元素即可。

但是，這題其實也可以用前一題學過的Bayer Moore投票演算法的模板來解。

第一輪選舉輪，先選出票數領先的前兩人。

第二輪驗證輪，驗票，檢驗領先的前兩人是否票數有超過n/3，若有，則放入最後的當選名單。

實作上有一個小細節，為什麼我們只需要選出領先的前兩人?
因為題目的規則是要超過n/3，透過簡單的反證法，可以證出最多只會有兩人有機會超過n/3

推廣題: 若題目改成超過n/k，則最多只會有(k-1)人有機會超過 n/k

程式碼

class Solution:
　def majorityElement(self, nums: List[int]) -> List[int]:
　　
　　# a list of majority elements
　　majority = []
　　
　　# threshold for majority validation and verification
　　threshold = len(nums) // 3
　　
　　# Record for possible majority candidates, at most two majority elements is allowed by math-proof.
　　candidate = [0, 0]
　　
　　# Voting for majority candidates
　　voting = [0, 0]
　　
　　## Step_#1:
　　# Find possible majority candidates
　　for number in nums:
　　　
　　　if number == candidate[0]:
　　　　# up vote to first candidate
　　　　voting[0] += 1
　　　　
　　　elif number == candidate[1]:
　　　　# up vote to second candidate
　　　　voting[1] += 1
　　　
　　　elif not voting[0]:
　　　　# set first candidate
　　　　candidate[0] = number
　　　　voting[0] = 1
　　　　
　　　elif not voting[1]:
　　　　# set second candidate
　　　　candidate[1] = number
　　　　voting[1] = 1
　　　　
　　　else:
　　　　# down vote if mis-match
　　　　voting[0] -= 1
　　　　voting[1] -= 1
　　
　　
　　## Step_#2:
　　# Validation:
　　voting = [0, 0]
　　
　　for number in nums:
　　　
　　　if number == candidate[0]:
　　　　# update up vote for first candidate
　　　　voting[0] += 1
　　　　
　　　elif number == candidate[1]:
　　　　# update up vote for second candidate
　　　　voting[1] += 1
　　
　　
　　for i, vote in enumerate(voting):
　　　
　　　# Verify majority by threshold
　　　if vote > threshold:
　　　　majority.append( candidate[i] )
　　　
　　　
　　return majority

複雜度分析

時間複雜度:

O( n ) 投票輪和驗證輪，複雜度皆為線性，各掃描一次。

空間複雜度:

O(1) majority, voting, candidate都是臨時變數，所占用的記憶體空間固定，都是常數級別O(1)

關鍵知識點

關鍵點在於聯想到用BM投票演算法找出領先者。

在前一題，我們用BM投票演算法找出票數最多的那一位，也稱之為眾數 mode。

在這一題，我們用BM投票演算法找出票數相對多的前k位，k=2，同時門檻票數要求超過 n/3。

Reference:

[1] Python O(1) aux space sol. by BM vote algorithm. [ With explanation ] - Majority Element II - LeetCode