題目敘述
題目會給定我們一個陣列，陣列長度為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:
