LeetCode 229 Majority Element II：摩爾投票法擴展求出現 > n/3 次元素

題目簡介

給定整數數組，找出所有出現次數 > ⌊n/3⌋ 的元素。要求 O(n) 時間，O(1) 空間。

解題思路：擴展摩爾投票法

出現 > n/3 次的元素最多 2 個。維護兩個候選數 cand1, cand2 及其計數 cnt1, cnt2：

• 遍歷數組，若當前數等於某候選，對應計數++。
• 否若某計數為 0，該候選替換為當前數，計數=1。
• 否則兩計數均--。

遍歷結束後，再統計兩候選實際出現次數，符合條件者加入結果。

代碼實現

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

複雜度分析

兩遍掃描，時間 O(n)，空間 O(1)。