---
# System prepended metadata

title: "\n    Leetcode 169. Majority Element\n"
tags: [Hash Table]

---

###### 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>