刷題日記(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) — — — — — — —
解題思路:摩爾投票法(成對移除)
- 取出list的第一個數放到一個暫存的變數(record)
- 然後將計數器counter設定為1 ,代表這個變數出現了一次
- 開始for迴圈,如果和(前面暫存的變數record)相等,則將計數器counter加1
- 如果和record不同且計數器>0時,將計數器 -1 (代表這兩個數成對移除了)
- 如果和record不同但是計數器=0時,將record更改為nums[i],並將計數器+1(代表前面的record已經成對移除完了,加入新的record)
- for迴圈跑完時,剩下的record就是答案(因為兩兩移除到最後剩下的一定是Major Element)


「時間/空間複雜度?」
(O(n), O(1),除了一些變數以外我們沒有使用到額外的空間)
— — — —(第二種hash map的解法,多了空間複雜度) — — — —
解題思路:
- new一個新的HashMap
- 先拿出list的第一個數
- 設定max=0, 然後size變數等於list的長度除2
- 開始跑for loop,如果從list拿出來的數Hashmap沒有就放入key和value 1
- 如果key已經在Hashmap裡了,就給key把value拿出來之後再+1放回去
- 如果value大於max, max等於該value值, 然後記錄一下目前的major element, 然後其中當得到的value已經超過list size的一半,表示後面的數值其他再怎麼追也不會超過它,可以直接return 目前紀錄的Major Element
- 否則最後迴圈結束return Major Element
