Java 尋找陣列中出現次數超過半數的元素與索引 (Boyer-Moore 投票演算法)

「最有效元素」定義為出現頻率超過陣列長度一半的元素。此問題可用 Boyer-Moore 多數投票演算法在 O(n) 時間、O(1) 空間 解決，但本文採用排序後計數的直觀做法 (O(n log n) 時間)，適合資料量不大或教學示範場景。

完整程式碼

import java.util.Arrays;

/**
 * 取得陣列中出現次數超過半數的元素及其所有索引。
 * @author 趙學慶 www.java2000.net
 */
public class MyTest {
    public static void main(String[] args) {
        int[] values = new int[] { 5, 3, 5, -5, 5, 0, 5 };
        int maxValue = getMax(values);
        if (maxValue > Integer.MIN_VALUE) {
            System.out.println("Number=" + maxValue);
            for (int i = 0; i < values.length; i++) {
                if (values[i] == maxValue) {
                    System.out.print(i + " ");
                }
            }
        } else {
            System.out.println("沒有找到");
        }
    }

    public static int getMax(int[] values) {
        int[] nums = Arrays.copyOf(values, values.length);
        Arrays.sort(nums);
        int number = Integer.MIN_VALUE;
        int count = 0;
        int numberTemp = Integer.MIN_VALUE;
        int countTemp = 0;

        for (int num : nums) {
            if (num == numberTemp) {
                countTemp++;
            } else {
                if (countTemp > count) {
                    number = numberTemp;
                    count = countTemp;
                }
                numberTemp = num;
                countTemp = 1;
            }
        }
        // 處理最後一組
        if (countTemp > count) {
            number = numberTemp;
            count = countTemp;
        }
        // 判斷是否超過半數
        if (1.0 * count / nums.length > 0.5) {
            return number;
        }
        return Integer.MIN_VALUE;
    }
}

執行結果

Number=5
0 2 4 6

演算法解析

1. 複製並排序：Arrays.copyOf 避免修改原陣列，排序後相同元素相鄰
2. 單次掃描計數：遍歷排序後陣列，累計相同值出現次數，記錄出現最多的值與次數
3. 邊界檢查：迴圈結束後需再比較最後一組計數
4. 多數判定：count > length / 2 即為「最有效元素」

複雜度與改進方向

Boyer-Moore 核心邏輯：維護候選元素 candidate 與計數器 count，遍歷陣列時相同則 count++，不同則 count--；count 歸零時更換候選元素。最終驗證候選元素是否真超過半數。

補充：取得所有索引位置

找到目標值後，再次遍歷原陣列 values 輸出索引，時間 O(n)，總體仍在可接受範圍。