目標：
這題主要目的在於介紹一個特別的演算法，
它叫做Boyer–Moore majority vote algorithm(摩爾投票算法)。
同時，接下來也會多介紹幾題陣列操作相關的題目。

原題：

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:
Input: [3,2,3]
Output: 3

Example 2:
Input: [2,2,1,1,1,2,2]
Output: 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個人取消他們的投票資格，會有以下的狀況：

1. 被取消資格的是B跟C -> 顯然A還是過半數(而且比例更高了XD)
2. 被取消資格的是(A, B)或(A, C) -> 一個投A的和一個不投A的同步被排除，
   所以無法改變A會過半數的狀況。

同理，在不只3個候選人(數字)的時候，每次取2個人取消投票資格(移除)，亦無法改變投票結果(A還是會是majority element)。

註：
所以我們可以知道，當你跟你的家人政治立場不同時，
只有兩個人的狀況下都不去投票是沒有用的，
有用的方式是在投票前夕帶著跟你立場相反的家人們出國去玩，
多於1人時，每多一個人你就多賺一張選票差距，但你的荷包可能會哭。
(不要說是我教的！)

依此，我們可以使用下列的方式來進行陣列運算：

1. 取出第一個數放到一個暫存的變數(res)，
   將計數器(cnt)設定為1，代表這個數出現1次。
2. 取出下一個數nums[i]，如果和res相等，則將計數器+1；
   如果和res不同，且計數器>0時，將計數器-1；(代表取這兩個數成對移除)
   如果和res不同但是計數器=0時，將res更改為nums[i]並將計數器+1
   (代表res已經用完了，現在還沒被移除的是nums[i])
3. 反覆進行步驟2直到陣列結尾，剩下的res即為答案。
   (因為兩兩移除到最後一定是非majority element的先被移光)

Java:

class Solution {
    public int majorityElement(int[] nums) {
        int res = nums[0], cnt = 1;
        
        // Boyer-Moore Voting Algorithm
        for (int i = 1; i < nums.length; ++i) {
            if (res == nums[i])
                cnt++;
            else if (cnt > 0)
                cnt--;
            else
                res = nums[i];
                cnt++;
        }
        return res;
    }
}

還有另一種作法，是將陣列進行排序，
無論如何majority element一定會通過中間的位置。
這種方式的時間複雜度為O(nlogn)，空間複雜度視你的呼叫方式而定，
可能是O(1)也可能是O(n)(將排序的結果放到別的地方的話)

Python:

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        res, cnt, l = nums[0], 1, len(nums)
        for i in range(1, l):
            if res == nums[i]:
                cnt += 1
            elif cnt > 0:
                cnt -= 1
            else:
                res = nums[i]                
                cnt += 1
        return res
        
'''
# sorting solution
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return sorted(nums)[len(nums)//2]
'''

面試實際可能會遇到的問題：
「時間/空間複雜度？」
(O(n), O(1)，除了一些變數以外我們沒有使用到額外的空間)

「各方法的優劣為何？」
(可以參照Solution的頁面，這篇作者分析的內容很完整)

從LeetCode學演算法，我們下次見囉，掰~

下篇預告：
0229. Majority Element II (Medium)