// 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
    }
};