【leetcode.229】求衆數Ⅱ

                                                     求衆數Ⅱ

一、要求

給定一個大小為 n 的數組，找出其中所有出現超過 ​

​⌊ n/3 ⌋​

​ 次的元素。

說明: 要求算法的時間複雜度為 O(n)，空間複雜度為 O(1)。

示例 1:

輸入: [3,2,3]
輸出: [3]      

示例 2:

輸入: [1,1,1,3,3,2,2,2]
輸出: [1,2]      

二、思路

這道題算是衆數Ⅰ的進階，有關衆數Ⅰ的解法，請參考我的另外一篇文章​​求衆數​​。

數組元素中出現次數超過n/3的元素，最多是兩個。是以我們設定變量a，b用來記錄目标元素，用aTimes，bTimes記錄對應元素出現的次數。

三、代碼實作

public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int a = 0;
        int b = 0;
        int aTimes = 0;
        int bTimes = 0;
        for (int temp : nums) {
            //當計數器為0時，需要變更a，但不能變更為與b相同的元素
            if ((aTimes == 0 && temp != b) || temp == a) {
                a = temp;
                aTimes++;
            } else if (bTimes == 0 || temp == b) {
                b = temp;
                bTimes++;
            } else {
                aTimes--;
                bTimes--;
            }
        }
        //統計兩個元素出現的次數
        int size = nums.length / 3;
        aTimes = 0;
        bTimes = 0;
        for (int c : nums) {
            if (c == a) {
                aTimes++;
            } else if (c == b) {
                bTimes++;
            }
        }
        if (aTimes > size) {
            list.add(a);
        }
        if (bTimes > size) {
            list.add(b);
        }
        return list;
    }