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