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