原文題目

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

題目摘要

1. 問題描述：給定一個長度為 n 的陣列 nums，找出「多數元素」。多數元素是指出現次數超過「n / 2」的元素。可以假設陣列中一定存在多數元素。
2. 輸入：一個長度為 n 的整數陣列 nums。
3. 輸出：多數元素，即出現次數超過「n / 2」次的那個元素。

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

解題思路

1. 多數元素的性質：
   • 題目保證多數元素出現次數超過 「n / 2」，這意味著該元素的出現次數多於陣列中的其他元素總和。
   • 因此，我們可以使用計票法來檢查哪個元素可以「抵消」其他元素，並最終找到多數元素。
2. 計票過程：
   • 遍歷陣列時，我們保持一個「候選者」(candidate) 和一個計數器 (count)。
   • 當計數器為 0 時，表示當前候選者被「抵消完畢」，需要將當前的元素設為新的候選者。
   • 若當前元素與候選者相同，則計數器加 1；若不同，則計數器減 1。
   • 最後，當遍歷完陣列後，候選者就是多數元素。

程式碼

class Solution { 
    public int majorityElement(int[] nums) { 
        int count = 0; //用來計算候選者的有效票數
        Integer candidate = null; //用來儲存目前的候選多數元素
        for (int num : nums) { 
            //若計票為0，則將當前元素設為候選者
            if (count == 0) {
                candidate = num;
            }
            //若當前元素與候選者相同，計票+1；否則-1
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
            // 可以將上面替換成簡化寫法：count += (num == candidate) ? 1 : -1;
        }
        return candidate; //回傳最終的候選者，因為題目保證多數元素一定存在
    }
}

結論： 這題「多數元素」問題其實有點像在一場會議裡，當大家都在發表不同的意見時，我們想找出那個最有影響力的聲音。透過這樣的處理方式，我們可以理解成當有人支持這個聲音時，計數加1，當有人反對時，計數減1。當計數變為零，代表大家的意見相抵了，需要換一個新的聲音繼續比較。最後，勝出的那個候選者就是支持度超過一半的多數意見。這個方法不僅簡潔，也不需要額外的空間，很適合大規模資料的處理。