LeetCode 多數元素問題解析與高效解法

問題描述

給定一個大小為 n 的數組，找出多數元素。多數元素是指在數組中出現次數大於 ⌊ n/2 ⌋ 的元素。假設數組非空且多數元素總是存在。

解法一：哈希表統計

最直觀的方法是使用哈希表統計每個元素出現的次數，然後遍歷哈希表找到出現次數超過 n/2 的元素。時間複雜度 O(n)，空間複雜度 O(n)。

public class Solution {
    public int majorityElement(int[] nums) {
        Map countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry entry : countMap.entrySet()) {
            if (entry.getValue() > nums.length / 2) {
                return entry.getKey();
            }
        }
        return -1; // 根據題意不會執行到這裡
    }
}

解法二：Boyer-Moore 投票算法（最優解）

該算法利用多數元素出現次數超過半數的特性，通過抵消非多數元素來找出多數元素。時間複雜度 O(n)，空間複雜度 O(1)。

核心思想： 維護一個候選元素 candidate 和計數器 count。遍歷數組：

• 若 count 為 0，將當前元素設為 candidate，count = 1。
• 若當前元素等於 candidate，count++；否則 count--。

遍歷結束後，candidate 即為多數元素（題目保證存在）。

public class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            } else if (nums[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
}

總結

哈希表解法易於理解，但需要額外空間；Boyer-Moore 算法空間優化極致，是面試中常考的最優解。根據場景選擇合適的解法。