刷題日記（6）Majority Element

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 exist in the array.

Example 1:

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

Example 2:

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

— — — — —— — (第一種很聰明的解法QAQ) — — — — — — —

解題思路：摩爾投票法(成對移除)

1. 取出list的第一個數放到一個暫存的變數（record）
2. 然後將計數器counter設定為1 ,代表這個變數出現了一次
3. 開始for迴圈，如果和(前面暫存的變數record)相等，則將計數器counter加1
4. 如果和record不同且計數器>0時，將計數器 -1 (代表這兩個數成對移除了)
5. 如果和record不同但是計數器=0時，將record更改為nums[i]，並將計數器+1（代表前面的record已經成對移除完了，加入新的record）
6. for迴圈跑完時，剩下的record就是答案（因為兩兩移除到最後剩下的一定是Major Element）

這段程式碼修改並來自https://ithelp.ithome.com.tw/articles/10213285，但不知為什麼leetcode的testcase過得了但正式run過不得了，不過應該是沒錯的

成對移除後只剩下最後一個2

「時間/空間複雜度？」
(O(n), O(1)，除了一些變數以外我們沒有使用到額外的空間)

— — — —(第二種hash map的解法,多了空間複雜度) — — — —

解題思路：

1. new一個新的HashMap
2. 先拿出list的第一個數
3. 設定max=0, 然後size變數等於list的長度除2
4. 開始跑for loop，如果從list拿出來的數Hashmap沒有就放入key和value 1
5. 如果key已經在Hashmap裡了，就給key把value拿出來之後再+1放回去
6. 如果value大於max, max等於該value值, 然後記錄一下目前的major element, 然後其中當得到的value已經超過list size的一半，表示後面的數值其他再怎麼追也不會超過它，可以直接return 目前紀錄的Major Element
7. 否則最後迴圈結束return Major Element