陣列入門題 用BM投票演算法 找眾數 Majority Element Leetcode #169

這題的題目在這裡:

題目敘述

題目會給定我們一個陣列，要求我們找出裡面出現次數最多的數字。

出現次數最多的數字也就是我們在統計上所謂的 眾數 mode

測試範例

Example 1:

Input: nums = [3,2,3]
Output: 3
3 出現最多次

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2
2 出現最多次​

約束條件

Constraints:

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

演算法

除了傳統的字典紀錄出現次數的演算法之外，
還有一個高效率的one-pass Bayer Morre Voting algorithm BM投票演算法。

原理很簡單，就是把每張票當成是對當下Majority候選人的同意票或否定票。

從左到右，掃描過每一個數字。票數初始化為0

當票數為零的時候，代表演算法剛開始，或者前一位候選人被Reset to zero，重新記錄新的Majority 候選人。

當票數不為零的時候，代表已經有一位潛在的Majority候選人。
假如當下這個數字和Majority候選人相同，代表是同意票，票數累加一。
假如當下這個數字和Majority候選人不同，代表是否定票，票數減一。

最後掃描完，留下來的Majority候選人就當選為真正的Majority，也是出現次數最多的數字，也就是我們在統計上所謂的 眾數 mode

程式碼

class Solution:
　def majorityElement(self, nums: List[int]) -> int:

　　voting = 0
　　candidate = 0

　　for number in nums:

　　　if voting == 0:
　　　　# 重新選一位潛在的Majority候選人
　　　　voting += 1
　　　　candidate = number
　　　
　　　elif number == candidate:
　　　　# 同意票
　　　　voting += 1
　　　
　　　else:
　　　　# 否定票
　　　　voting -= 1

　　return candidate
　　

複雜度分析

時間複雜度:

O( n ) 只需要掃描整個陣列一次。

空間複雜度:

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

關鍵知識點

Bayer Morre Voting algorithm BM投票演算法是一個在O(n)內尋找眾數的演算法。

和傳統的字典演算法相比，省去了建造字典的空間，BM投票演算法在空間上更為精簡。

Reference:

[1] Python/JS/Go O(n) by BM algorithm [w/ Reference] - Majority Element - LeetCode