169. Majority Element

題目 / Problem

中文： 給定一個大小為 n 的陣列 nums，回傳其中的「多數元素 (majority element)」。

多數元素是指在陣列中出現次數嚴格大於 ⌊n / 2⌋ 的元素。你可以假設陣列中一定存在這樣的元素。

English: Given an array nums of size n, return the majority element — the element that appears strictly more than ⌊n / 2⌋ times. You may assume the majority element always exists.

Constraints: - 1 <= n <= 5 * 10^4 - -10^9 <= nums[i] <= 10^9 - A majority element is guaranteed to exist.

Worked example: - Input: nums = [2,2,1,1,1,2,2] (length 7, so ⌊7/2⌋ = 3) - 2 appears 4 times (> 3), so the answer is 2.

名詞解釋 / Glossary

• Majority element / 多數元素：在長度為 n 的陣列中出現次數嚴格大於 n/2 的元素。因為超過一半，這種元素至多只會有一個 / The element appearing strictly more than n/2 times. Because it occupies more than half the array, at most one such element can exist.
• Hash map (hash table) / 雜湊表：一種能以平均 O(1) 時間做 key→value 查找與更新的資料結構。C 語言沒有內建，C++ 有 std::unordered_map / A data structure offering average O(1) lookup/insert. C has no built-in version; C++ provides std::unordered_map.
• Boyer–Moore 投票演算法 / Boyer–Moore Voting Algorithm：一種只用兩個變數（候選者 candidate、計數器 count）就能在 O(n) 時間、O(1) 空間找出多數元素的經典演算法 / A classical algorithm that finds the majority element in O(n) time and O(1) space using only two variables: a candidate and a counter.
• Candidate / 候選者：投票過程中目前「暫時領先」的元素。當計數器歸零時，會被換成下一個元素 / The currently "leading" element during the voting pass. When the counter hits zero, it gets replaced by the next element.
• Counter / 計數器：候選者的「淨領先票數」。遇到相同元素 +1，遇到不同元素 −1 / The candidate's net lead. Same element → +1, different element → −1.
• In-place / 原地：不額外配置與輸入大小成正比的記憶體。Boyer–Moore 就是 in-place 的（只用常數變數）/ Using only constant extra memory, no array proportional to input size. Boyer–Moore qualifies.
• Function signature / 函式簽名：函式的名字、參數型別與回傳型別。LeetCode 的 C 版本是 int majorityElement(int* nums, int numsSize) / The function's name, parameter types, and return type. LeetCode's C version is int majorityElement(int* nums, int numsSize).

思路

最直觀的暴力解是：對每個元素，掃一次整個陣列數它出現幾次，遇到次數 > n/2 就回傳。這需要 O(n²) 時間，當 n = 5×10⁴ 時會接近 2.5×10⁹ 次操作，太慢。第二種改進是排序後回傳中間位置 nums[n/2]：因為多數元素超過一半，排序後它一定會「跨越」中間位置，這個解法 O(n log n)、O(1) 額外空間（若允許就地排序）。第三種是用雜湊表記錄每個元素的出現次數，O(n) 時間但需要 O(n) 空間。最佳解是 Boyer–Moore 投票演算法：只用一個候選者 cand 和一個計數器 count。掃過陣列時，若 count == 0 就把目前元素設為新候選者；接著如果目前元素等於候選者就 count++，否則 count--。直覺上每一個「非候選者」的票都會抵消一張「候選者」的票，因為多數元素超過一半，它的票永遠抵消不完，最後留下來的候選者一定是多數元素。這個演算法做到 O(n) 時間、O(1) 空間，正好回應題目的 follow-up。

The brute-force approach counts occurrences of each element with a nested loop — O(n²) time, which is too slow when n is up to 5×10⁴. A better idea is to sort the array and return nums[n/2]: because the majority element occupies more than half the slots, it must straddle the middle index after sorting. That gives O(n log n). Using a hash map to count frequencies achieves O(n) time but costs O(n) space. The optimal solution is the Boyer–Moore voting algorithm: maintain a single candidate cand and a counter count. Walk through the array; whenever count == 0, adopt the current element as the new candidate. Then count++ if the current element matches the candidate, else count--. The intuition is that every non-majority vote can cancel exactly one majority vote, but since the majority element holds more than half the votes, its votes can never be fully cancelled — whoever remains as the candidate at the end must be the majority element. This achieves O(n) time and O(1) space, satisfying the follow-up.

逐步走查 / Walkthrough

Tracing Boyer–Moore on nums = [2,2,1,1,1,2,2] (n = 7, threshold = 3):

Final candidate / 最終候選者 = 2 ✓ (matches expected output).

Solution — C

// Algorithm: Boyer–Moore voting / Boyer–Moore 投票演算法
// Maintain one candidate and one counter. When counter hits zero, adopt the
// current element as the new candidate. Same element → +1, different → −1.
// 維護一個候選者與一個計數器；計數歸零時換候選者，相同 +1，不同 −1。
// O(n) time, O(1) extra space — satisfies the follow-up.

int majorityElement(int* nums, int numsSize) {
    int cand = 0;          // 候選者，初值任意（count=0 時會立刻被覆寫）/ candidate; any init value, will be overwritten when count==0
    int count = 0;         // 候選者目前的淨票數 / current net vote count for the candidate

    for (int i = 0; i < numsSize; i++) {   // 遍歷整個陣列一次 / single pass over the array
        if (count == 0) {                  // 沒有有效候選者時 / no active candidate
            cand = nums[i];                // 把當前元素當作新候選者 / adopt current element as new candidate
        }
        if (nums[i] == cand) {             // 當前元素和候選者相同 / current element matches candidate
            count++;                       // 票數 +1 / vote up
        } else {                           // 否則 / otherwise
            count--;                       // 票數 −1（一張反對票抵消一張贊成票）/ vote down (one opposing vote cancels one supporting vote)
        }
    }

    return cand;  // 題目保證多數元素存在，最後的候選者就是答案 / problem guarantees existence, so final candidate is the answer
}

Solution — C++

// Algorithm: Boyer–Moore voting / Boyer–Moore 投票演算法
// Same idea as the C version — one candidate, one counter, single pass.
// 與 C 版相同：一個候選者、一個計數器、掃一次陣列。
// O(n) time, O(1) extra space.

#include <vector>   // 提供 std::vector / provides std::vector

class Solution {
public:
    int majorityElement(std::vector<int>& nums) {   // vector<int>& 是「整數陣列的參考」，避免複製整個陣列 / reference to vector<int> avoids copying the input
        int cand = 0;        // 候選者 / candidate (init value irrelevant; reset when count==0)
        int count = 0;       // 候選者的淨票數 / net vote count for the candidate

        for (int x : nums) {              // range-for：依序把每個元素複製到 x / range-for iterates each element as x
            if (count == 0) {             // 沒有有效候選者時 / no active candidate
                cand = x;                 // 採用 x 當新候選者 / adopt x as the new candidate
            }
            if (x == cand) {              // 與候選者相同 / matches candidate
                ++count;                  // 票 +1（前置遞增與後置等價，習慣寫法）/ increment counter (pre-increment, idiomatic in C++)
            } else {                      // 否則 / otherwise
                --count;                  // 票 −1 / decrement counter
            }
        }

        return cand;  // 多數元素一定存活到最後 / the majority element is guaranteed to survive as the final candidate
    }
};

複雜度 / Complexity

• Time: O(n) — 我們只對陣列做一次線性掃描，每個元素做常數次比較與加減運算 / We make a single linear pass over the array, doing constant work (one compare, one increment/decrement) per element. n is the length of nums.
• Space: O(1) — 只用了兩個 int 變數（cand 與 count），與輸入大小無關 / Only two int variables (cand, count) are used regardless of input size.

Pitfalls & Edge Cases

• 計數歸零時的順序 / Order when count reaches zero：必須先檢查 count == 0 再做 count++/--，否則新候選者會被立刻記為 count = 0（不同）而扣分 / You must check count == 0 before updating the counter; otherwise the freshly-adopted candidate would immediately get its count decremented because of the comparison logic.
• 演算法假設多數元素存在 / Algorithm assumes a majority exists：Boyer–Moore 一定會回傳一個 cand，但若沒有真正的多數元素，這個 cand 可能不正確。本題保證存在，所以不需要第二次驗證。在實際工作中若不保證，需要再掃一次計數確認 / Boyer–Moore always returns some candidate, but if no true majority exists, that candidate may be wrong. This problem guarantees existence, so no verification pass is needed; in real-world use without that guarantee, do a second pass to count cand and confirm it exceeds n/2.
• 整數範圍 / Integer range：nums[i] 可達 ±10⁹，仍在 32-bit int 範圍 (約 ±2.1×10⁹) 內，所以用 int 儲存候選者沒問題 / Values fit in 32-bit int (range ≈ ±2.1×10⁹), so storing the candidate as int is safe — no overflow risk.
• 單一元素陣列 / Single-element array：n == 1 時，那個元素出現 1 次 > ⌊1/2⌋ = 0，自身就是多數元素。第一輪迴圈會把它設為 cand 並 count = 1，正確回傳 / When n == 1, the lone element trivially qualifies (1 > 0). The first iteration sets it as cand with count = 1, returning correctly.
• 不要用 nums[0] 初始化並從 i = 1 開始的「最佳化」/ Don't "optimize" by initializing with nums[0] and starting from i = 1：邏輯上沒錯，但容易在計數規則上寫錯（例如忘記第一張票）。從 count = 0 與索引 0 開始最不易出錯 / It works logically but is error-prone (easy to miscount the first vote). Starting with count = 0 from index 0 is the safest formulation.