目標：
這題主要目的在於進一步討論摩爾投票算法的延伸。

原題：

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:
Input: [3,2,3]
Output: [3]

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

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

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

Java:

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0)
            return res;
        int n1 = 0, n2 = 1, cnt1 = 0, cnt2 = 0;
        for (int num : nums) {
            if (num == n1) {
                ++cnt1;
            } else if (num == n2) {
                ++cnt2;
            } else if (cnt1 == 0) {
                n1 = num;
                cnt1 = 1;
            } else if (cnt2 == 0) {
                n2 = num;
                cnt2 = 1;
            } else {
                --cnt1;
                --cnt2;
            }
        }
        cnt1 = 0;
        cnt2 = 0;
        
        for (int num : nums) {
            if (num == n1) 
                ++cnt1;
            else if (num == n2)
                ++cnt2;
        }
        
        int len = nums.length;
        if (cnt1 > len / 3)
            res.add(n1);
        if (cnt2 > len / 3)
            res.add(n2);
        return res;
    }
}

Python的部分，我們這邊除了同於Java的解法以外，
再提供一個簡單的作法：使用Counter。
利用Counter可以將一個列表轉換成Counter物件，
儲存的方式是(key:元素 及 value: 該元素出現的次數)
在迴圈中的取用基本上跟字典類似。
只要檢查每個元素出現次數是否大於三分之一的數量即可加至結果。
(請留意如果認真按照題目要求的話，這個解法因為會佔用額外O(n)空間，
故不是一個在O(1)空間內可以完成的算法。)

Python:

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        n1, n2, cnt1, cnt2 = 0, 1, 0, 0
        for num in nums:
            if num == n1:
                cnt1 += 1
            elif num == n2:
                cnt2 += 1
            elif cnt1 == 0:
                n1 = num
                cnt1 = 1
            elif cnt2 == 0:
                n2 = num
                cnt2 = 1
            else:
                cnt1 -= 1
                cnt2 -= 1
        
        cnt1, cnt2 = 0, 0
        
        for num in nums:
            if num == n1:
                cnt1 += 1
            elif num == n2:
                cnt2 += 1
        
        res, l = [], len(nums)
        if cnt1 > l // 3:
            res.append(n1)
        if cnt2 > l // 3:
            res.append(n2)
            
        return res
                
'''
# Using Counter but need extra space
from collections import Counter
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        constraint = len(nums) // 3
        count = Counter(nums)
        res = []
        for k, v in count.items():
            if v > constraint:
                res.append(k)
            
        return res
'''

面試實際可能會遇到的問題：
「時間/空間複雜度？」
(O(n), O(1)。
要經過整個陣列兩次，且額外並沒有需求常數次數以外的空間)

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

下篇預告：
0063. Unique Paths II (Medium)