###### tags: `Hash Table`
<h1>
Leetcode 169. Majority Element
</h1>
<ol>
<li>問題描述</li>
Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.<br><br>

Example 1:

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

Example 2:

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

<li>Input的限制</li>
<ul>
<li>n == nums.length</li>
<li>1 <= n <= 5 * 10^4</li>
<li>-10^9 <= nums[i] <= 10^9</li>
</ul>
<br>

<li>思考流程</li>
<ul>
<li>HashMap</li>
因為是要找陣列裡面的 majority element，所以它一定是陣列裡面出現最多次的元素。利用 hash table(python 的 dict.)來記錄每個元素出現的次數，遍歷完整個陣列後，就可知 majority element 是誰。
<br>
<br>
最差的情況下，hash table 會記錄 ⌊n / 2⌋ - 1 個陣列元素，故 space complexity 是 O(n)。
<br>
<br>
Time Complexity: O(n); Space Complexity: O(n)
<br>
<br>
<li>Boyer-Moore voting algorithm</li>
因為 majority elemnts 會多於 non-majority elements，我們用數數量的方式來找出 majority element，當 count 為 0 的時候，因為之前認定的 element 數量上少於其他 element，所以就不是 majority element。這時候會猜測當前的 element 為 majority element，直到 count 再為 0 為止才會更換。
<br>
<br>
Time complexity 的部分因為需遍歷整個陣列，所以是 O(n); Space complexity 的部分，因為只花了常數個變數，故 space complexity 為 O(1)。
<br>
<br>
Time Complexity: O(n); Space Complexity: O(1)
<br>
<br>
</ul>
<li>測試</li>
<ul>
<li>test 1</li>
Input:[5, 2, 3, 5, 5] Output:5。
<li>Input is empty list( edge case )</li>
如果輸入的是空陣列，則必須產生錯誤訊息。
</ol>