0169. Majority Element (Easy)
Question
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exists in the array.
Example 1
| |
Example 2
| |
分析/解題
嗨，大家今天過得好嗎？歡迎回到軟工宅宅(誤)。
接下來的幾題我們會著墨一下有關陣列(Array)或列表(List)相關的內容。
題目給定了一個長度為n的陣列，
已知當中有一個majority element(佔大多數的元素)，
這個數的個數會多過於⌊ n/2 ⌋。
(此符號代表向下取整數，如⌊ 5/2 ⌋=2。
別忘了是more than，所以如果n是5的話，
代表majority element至少要有3個)
題目還貼心地告訴我們，可以假定陣列不是空的，
且一定存在majority element，所以這邊可以省掉一些常用的檢查。
怎麼解這題呢？
一般來說的直覺可能會想使用HashMap來解(Python則用dict)，
將每個數塞入HashMap/字典中，最後找最大的那個數就是了。
這麼做的時間複雜度為O(n)，空間複雜度亦為O(n)，
因為插入耗費的時間為O(1)，插入n個數即為O(n)，
同時，我們只能保證最多有n - ⌊ n/2 ⌋的不同種類的數，
所以空間上還是保持在O(n)的複雜度。
在中途過程中在去檢驗是否有超過半數的element也可以，
但由於過程不保證會先碰到超過半數，所以額外檢驗的時間，
和省下來後面可能不用做完的時間相比，是不能肯定誰效率比較好的。
那麼，有沒有比較節省空間的做法呢？
有的！這裡介紹一個演算法，全名叫做：
Boyer–Moore majority vote algorithm(摩爾投票算法)
這個算法的核心在於，
刪去一個數列中的兩個不同的數字，不會影響該數列的majority element。
假想有一群人要投票，候選人有A、B、C，假設A已知會過半數的話，
任取其中2個人取消他們的投票資格，會有以下的狀況：
- 被取消資格的是B跟C -> 顯然A還是過半數(而且比例更高了XD)
- 被取消資格的是(A, B)或(A, C) -> 一個投A的和一個不投A的同步被排除，所以無法改變A會過半數的狀況。
同理，在不只3個候選人(數字)的時候，每次取2個人取消投票資格(移除)，亦無法改變投票結果(A還是會是majority element)。
註：
所以我們可以知道，當你跟你的家人政治立場不同時，
只有兩個人的狀況下都不去投票是沒有用的，
有用的方式是在投票前夕帶著跟你立場相反的家人們出國去玩 ，
多於1人時，每多一個人你就多賺一張選票差距 ，但你的荷包可能會哭。
(不要說是我教的！)
依此，我們可以使用下列的方式來進行陣列運算：
- 取出第一個數放到一個暫存的變數(res)，
將計數器(cnt)設定為1，代表這個數出現1次。 - 取出下一個數nums[i]，如果和res相等，則將計數器+1；
如果和res不同，且計數器>0時，將計數器-1；(代表取這兩個數成對移除)
如果和res不同但是計數器=0時，將res更改為nums[i]並將計數器+1(代表res已經用完了，現在還沒被移除的是nums[i]) - 反覆進行步驟2直到陣列結尾，剩下的res即為答案。
(因為兩兩移除到最後一定是非majority element的先被移光)
Java
還有另一種作法，是將陣列進行排序，
無論如何majority element一定會通過中間的位置。
這種方式的時間複雜度為O(nlogn)，空間複雜度視你的呼叫方式而定，
可能是O(1)也可能是O(n)(將排序的結果放到別的地方的話)
Python
面試實際可能會遇到的問題
「時間/空間複雜度？」
(O(n), O(1)，除了一些變數以外我們沒有使用到額外的空間)
「各方法的優劣為何？」
(可以參照Solution的頁面，這篇作者分析的內容很完整)
從LeetCode學演算法，我們下次見囉，掰~