0229. Majority Element II (Medium)

Question

Given an integer array of size n, 
find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1

1
2

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

Example 2

1
2

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

分析/解題

跟上一篇相似，這篇將出現超過二分之一改變為三分之一，
要求求所有出現超過三分之一次數的數值，
這使得可能超過三分之一的種類會變成2種，但並不保證一定會有2種。
按照上一篇的摩爾投票算法的思路，
我們可以取2個數(n1, n2)暫存，
每次拿一個新的來檢驗並處理每三個相消的動作，
這樣我們即可以保證留下來的會有當中超過三分之一的元素。

要特別留意的是，兩個數有可能會是一致的，
且不一定每次都存在2種超過三分之一的元素，
所以最後我們要個別重新確認留在n1及n2上的元素，
其個數是否有超過三分之一。

Java

Python的部分，我們這邊除了同於Java的解法以外，
再提供一個簡單的作法：使用Counter。
利用Counter可以將一個列表轉換成Counter物件，
儲存的方式是(key:元素 及 value: 該元素出現的次數)
在迴圈中的取用基本上跟字典類似。
只要檢查每個元素出現次數是否大於三分之一的數量即可加至結果。

(請留意如果認真按照題目要求的話，
這個解法因為會佔用額外O(n) 空間，
故不是一個在O(1)空間內可以完成的算法。)

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(n), O(1)。
要經過整個陣列兩次，且額外並沒有需求常數次數以外的空間)

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