leetcode | Easy | 169. Majority Element

更新於 發佈於 閱讀時間約 6 分鐘
這題是面試中常見的經典題目,要求從一個陣列裡找出出現次數超過一半的元素,也就是所謂的「眾數」。為了更好理解,會先用一個直觀、易懂的方式來解釋問題,透過哈希表的方法來找出答案。接著,我會介紹一個更快、更有效率的解法,也就是 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 時,將當前元素設為新的 candidatecount 重置為 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 !

留言
avatar-img
留言分享你的想法!
avatar-img
Hua的沙龍
9會員
8內容數
成功考上研究所,當面對大量的文獻資源時,你可能感到茫然不知如何開始閱讀,也或許不確定該如何開始撰寫畢業論文。在這裡,我將與你分享一些與做研究相關的實用技巧,期望這份指南能夠為初次踏入研究領域的新手帶來實質的協助。
Hua的沙龍的其他內容
2024/11/06
本文介紹了兩種將長度為 n 的陣列元素向右旋轉 k 個位置的方法,分別為使用額外陣列的直觀解法和不使用額外空間的反轉法。本文提供了時間複雜度分析及 C++ 程式碼示例,幫助讀者理解這兩種解法的不同優缺點,並適用於不同情況中的應用。
Thumbnail
2024/11/06
本文介紹了兩種將長度為 n 的陣列元素向右旋轉 k 個位置的方法,分別為使用額外陣列的直觀解法和不使用額外空間的反轉法。本文提供了時間複雜度分析及 C++ 程式碼示例,幫助讀者理解這兩種解法的不同優缺點,並適用於不同情況中的應用。
Thumbnail
2024/11/03
這個問題「Remove Duplicates from Sorted Array」要求我們從一個已排序的陣列中移除重複的元素,並且返回移除後的陣列新長度。由於陣列已經是排序好的,所以所有的重複元素會是相鄰的。 我們需要移除重複的元素,使每個元素最多只出現一次,並返回去重後的陣列長度。不能使用額外的空
Thumbnail
2024/11/03
這個問題「Remove Duplicates from Sorted Array」要求我們從一個已排序的陣列中移除重複的元素,並且返回移除後的陣列新長度。由於陣列已經是排序好的,所以所有的重複元素會是相鄰的。 我們需要移除重複的元素,使每個元素最多只出現一次,並返回去重後的陣列長度。不能使用額外的空
Thumbnail
2024/11/03
今天介紹 LeetCode 「Container With Most Water」,分享兩種解法,包括暴力法和雙指針法。透過 C++ 的逐行解讀,幫助讀者更有效地思考問題,尤其在時間複雜度方面的差異,對於學習演算法與程式設計都有所幫助。
Thumbnail
2024/11/03
今天介紹 LeetCode 「Container With Most Water」,分享兩種解法,包括暴力法和雙指針法。透過 C++ 的逐行解讀,幫助讀者更有效地思考問題,尤其在時間複雜度方面的差異,對於學習演算法與程式設計都有所幫助。
Thumbnail
看更多
你可能也想看
Thumbnail
TOMICA第一波推出吉伊卡哇聯名小車車的時候馬上就被搶購一空,一直很扼腕當時沒有趕緊入手。前陣子閒來無事逛蝦皮,突然發現幾家商場都又開始重新上架,價格也都回到正常水準,估計是官方又再補了一批貨,想都沒想就立刻下單! 同文也跟大家分享近期蝦皮購物紀錄、好用推薦、蝦皮分潤計畫的聯盟行銷!
Thumbnail
TOMICA第一波推出吉伊卡哇聯名小車車的時候馬上就被搶購一空,一直很扼腕當時沒有趕緊入手。前陣子閒來無事逛蝦皮,突然發現幾家商場都又開始重新上架,價格也都回到正常水準,估計是官方又再補了一批貨,想都沒想就立刻下單! 同文也跟大家分享近期蝦皮購物紀錄、好用推薦、蝦皮分潤計畫的聯盟行銷!
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
這題是面試中常見的經典題目,要求從一個陣列裡找出出現次數超過一半的元素,也就是所謂的「眾數」。為了更好理解,會先用一個直觀、易懂的方式來解釋問題,透過哈希表的方法來找出答案。接著,我會介紹一個更快、更有效率的解法,也就是 Boyer-Moore 多數投票算法。
Thumbnail
這題是面試中常見的經典題目,要求從一個陣列裡找出出現次數超過一半的元素,也就是所謂的「眾數」。為了更好理解,會先用一個直觀、易懂的方式來解釋問題,透過哈希表的方法來找出答案。接著,我會介紹一個更快、更有效率的解法,也就是 Boyer-Moore 多數投票算法。
Thumbnail
成對的數字裡出現一個落單的邊緣人,我有六種方法找出它,你會幾種呢?
Thumbnail
成對的數字裡出現一個落單的邊緣人,我有六種方法找出它,你會幾種呢?
Thumbnail
347. Top K Frequent Elements 解題
Thumbnail
347. Top K Frequent Elements 解題
Thumbnail
題目摘要: 在這篇文章中,我們將討論如何使用摩爾投票算法找出一個陣列中的「主要元素」。主要元素指的是在陣列中出現次數超過一半的元素,並且我們可以確定它一定存在於陣列中。這個算法的核心思想和應用將在本文中被詳細介紹。 題目知識點: 主要元素的定義和重要性。 摩爾投票算法的工作原理和優點。 先備知識
Thumbnail
題目摘要: 在這篇文章中,我們將討論如何使用摩爾投票算法找出一個陣列中的「主要元素」。主要元素指的是在陣列中出現次數超過一半的元素,並且我們可以確定它一定存在於陣列中。這個算法的核心思想和應用將在本文中被詳細介紹。 題目知識點: 主要元素的定義和重要性。 摩爾投票算法的工作原理和優點。 先備知識
Thumbnail
題目會給定我們一個陣列,要求我們找出裡面統計最多出現次數的偶數 。 假如有兩個偶數出現的次數一樣多,取最數字比較小的那個最為答案。
Thumbnail
題目會給定我們一個陣列,要求我們找出裡面統計最多出現次數的偶數 。 假如有兩個偶數出現的次數一樣多,取最數字比較小的那個最為答案。
Thumbnail
題目會給定我們一個陣列,陣列長度為n。 要求我們找出裡面出現次數超過 n / 3次的數字。
Thumbnail
題目會給定我們一個陣列,陣列長度為n。 要求我們找出裡面出現次數超過 n / 3次的數字。
Thumbnail
題目會給定我們一個陣列,要求我們找出裡面出現次數最多的數字。 出現次數最多的數字也就是我們在統計上所謂的 眾數 mode
Thumbnail
題目會給定我們一個陣列,要求我們找出裡面出現次數最多的數字。 出現次數最多的數字也就是我們在統計上所謂的 眾數 mode
Thumbnail
題目會給我們一個排序好的陣列,還有一個目標值target 要求我們在陣列中尋找target所在的索引位置。 如果target 不存在,返回-1 題目要求必須在O( log n )對數時間內完成 。
Thumbnail
題目會給我們一個排序好的陣列,還有一個目標值target 要求我們在陣列中尋找target所在的索引位置。 如果target 不存在,返回-1 題目要求必須在O( log n )對數時間內完成 。
Thumbnail
這題就是經典的考排序驗算法, 不管在教科書、上機考、面試白板題都是一個很基本又滿熱門的題目。 題目會給定一個輸入陣列,要求我們實作一個排序演算法,把陣列元素從小到大排好。
Thumbnail
這題就是經典的考排序驗算法, 不管在教科書、上機考、面試白板題都是一個很基本又滿熱門的題目。 題目會給定一個輸入陣列,要求我們實作一個排序演算法,把陣列元素從小到大排好。
Thumbnail
題目會給我們一個輸入陣列,長度為n+1。 陣列裡面會有n+1個數字,數字的範圍從1到n 裡面恰好有一個數字重複出現,要求我們找出那個重複的數字。 題目要求只能使用常數空間O(1),並且限制不能修改陣列內容。
Thumbnail
題目會給我們一個輸入陣列,長度為n+1。 陣列裡面會有n+1個數字,數字的範圍從1到n 裡面恰好有一個數字重複出現,要求我們找出那個重複的數字。 題目要求只能使用常數空間O(1),並且限制不能修改陣列內容。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News