leetcode | Easy | 169. Majority Element

題目: https://leetcode.com/problems/majority-element/

這題是面試中常見的經典題目，要求從一個陣列裡找出出現次數超過一半的元素，也就是所謂的「眾數」。為了更好理解，會先用一個直觀、易懂的方式來解釋問題，透過哈希表的方法來找出答案。接著，我會介紹一個更快、更有效率的解法，也就是 Boyer-Moore 多數投票算法。

解法一：直觀解法（使用哈希表）

我們可以使用一個哈希表（例如 C++ 中的 unordered_map）來記錄每個元素出現的次數。遍歷陣列時，對每個元素進行計數，然後檢查該元素的出現次數是否超過 n/2。

時間複雜度：O(n)

其中 n 是陣列的長度。我們只需遍歷一次陣列。

C++程式碼：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        std::unordered_map<int, int> countMap;
        int majorityCount = nums.size() / 2;

        for (int num : nums) {
            ++countMap[num];
            if (countMap[num] > majorityCount) {
                return num;
            }
        }

        // 根據題意，眾數一定存在，因此這裡不需要額外處理
        return -1; // 這行實際上永遠不會被執行
    }
};

解釋：

• 建立哈希表： 使用 unordered_map<int, int> countMap 來存儲每個數字及其出現次數。
• 遍歷陣列： 使用範圍循環 for (int num : nums) 遍歷每個元素。
• 計數並檢查：
• • 對當前元素 num，增量其在 countMap 中的計數。
  • 如果 countMap[num] 超過 majorityCount（即 n/2），則返回該元素，因為它是眾數。
• 返回結果： 根據題目保證眾數一定存在，因此我們在找到眾數後直接返回

解法二：Boyer-Moore (多數投票算法)

Boyer-Moore 多數投票算法是一種線性時間、常數空間的算法。核心思想是：

• 設定一個候選人 candidate，初始為陣列的第一個元素。
• 設定一個計數器 count，初始為 1。
• 遍歷陣列，當遇到與 candidate 相同的元素時，count 加 1；否則，count 減 1。
• 當 count 為 0 時，將當前元素設為新的 candidate，count 重置為 1。
• 最終，candidate 即為眾數。

時間複雜度：O(n)

其中 n 是陣列的長度。我們只需遍歷一次陣列。

C++程式碼：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = nums[0];
        int count = 1;

        for (size_t i = 1; i < nums.size(); ++i) {
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            } else if (nums[i] == candidate) {
                ++count;
            } else {
                --count;
            }
        }

        return candidate;
    }
};

解釋：

• 初始化候選人和計數器：
• • candidate 初始化為 nums[0]。
  • count 初始化為 1。
• 遍歷陣列：
• • 如果 count 為 0：將當前元素設為新的 candidate。將 count 重置為 1。
  • 如果當前元素等於 candidate：將 count 增加 1。
  • 否則：將 count 減少 1。
• 返回結果： 最終的 candidate 即為眾數。

為什麼這個算法可行？

• 由於眾數出現的次數超過 n/2，其他元素的總數加起來也無法超過眾數的出現次數。
• 在配對消除的過程中，眾數最終會成為剩下的候選人。

以上是 Hua 在 LeetCode 的解題分享，有想法或是建議歡迎在底下討論。

Day Day Good, Day Day Up !