尋找數組中出現次數超過一半的數字：四種 Java 實現方案與複雜度分析

問題描述

給定一個整數陣列，找出出現次數超過陣列長度一半的數字（假設一定存在）。

方案一：排序法

陣列排序後，中位數即為所求。

• 時間複雜度：O(N log N)（快速排序）
• 空間複雜度：O(1) 或 O(log N)（遞迴堆疊）

方案二：哈希表統計法

用 HashMap 統計每個數字出現次數，遍歷找出超過半數者。

• 時間複雜度：O(N)
• 空間複雜度：O(N)

方案三：摩爾投票法——最優解

核心思想：目標數字出現次數超過所有其他數字之和。遍歷時維護一個候選數字與計數器，相同則加一，不同則減一；計數歸零時更換候選。最終候選即為答案。

• 時間複雜度：O(N)
• 空間複雜度：O(1)

public int moreThanHalfNum(int[] nums) {
    if (nums == null || nums.length == 0) return -1;
    int candidate = nums[0];
    int count = 1;
    for (int i = 1; i < nums.length; i++) {
        if (count == 0) {
            candidate = nums[i];
            count = 1;
            continue;
        }
        if (candidate == nums[i]) count++;
        else count--;
    }
    return candidate;
}

方案四：改良快速選擇算法

利用快排的 Partition 過程，每次將基準值放到正確位置。若基準位置等於中間索引，即找到中位數；否則在左或右區間繼續遞迴。

• 平均時間複雜度：O(N)
• 最壞時間複雜度：O(N²)
• 空間複雜度：O(1)

public int partition(int[] nums, int start, int end) {
    int pivot = nums[start];
    int origin = start;
    while (start < end) {
        while (start < end && nums[end] >= pivot) end--;
        while (start < end && nums[start] < pivot) start++;
        swap(nums, start, end);
    }
    swap(nums, origin, end);
    return end;
}

public int moreThanHalfNumQuickSelect(int[] nums) {
    if (nums.length == 0) return -1;
    int start = 0, end = nums.length - 1;
    int mid = nums.length / 2;
    int index = partition(nums, start, end);
    while (index != mid) {
        if (index > mid) index = partition(nums, start, index - 1);
        else index = partition(nums, index + 1, end);
    }
    return nums[index];
}

總結

實際開發中推薦摩爾投票法（方案三），時間空間皆優，代碼簡潔。面試常考察此思路。