【Warrior刷題筆記】力扣169. 多數元素 【排序 || 哈希 || 隨機演算法 || 摩爾投票法】詳細注釋 不斷優化 極致壓榨

題目

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/majority-element/
注意，該題在LC中被標注為easy，所以我們更多應該關注的是文章中不斷優化的思路和方法，很多時候面試考察的，就是與面試官一起做題并把時間復雜度和空間復雜度壓榨到極致的程序中你所表現出來的能力，

1.描述

給定一個大小為 n 的陣列，找到其中的多數元素，多數元素是指在陣列中出現次數大于 ?n/2?的元素，
你可以假設陣列是非空的，并且給定的陣列總是存在多數元素，

2.示例

• 示例 1：

	輸入：[3,2,3]
	輸出：3

• 示例 2：

	輸入：[2,2,1,1,1,2,2]
	輸出：2

解法一 排序

解題思路

很快啊，啪的一下我們想到，由于多數元素是指在陣列中出現次數 大于 ?n/2? 的元素，那么將陣列排序后，即便該元素是最小元素或是最大元素，其在陣列中的覆寫范圍也超過了陣列中點（從左到右超過或是從右到左超過），于是得到演算法：

演算法

1.將陣列排序；
2.回傳陣列中點元素nums[nums.size()/2].

代碼

1 class Solution {
2 public:
3     int majorityElement(vector<int>& nums) {
4         sort(nums.begin(), nums.end());//對陣列進行排序
5         return nums[nums.size()/2];//回傳陣列中點元素
6     }
7 };

復雜度分析

時間復雜度： O(mlogm)，m為陣列元素數，主要是排序的時間消耗，
空間復雜度： O(logm)，主要是系統sort函式需要的堆疊空間消耗，

解法二 哈希

解題思路

這時候，面試官說，你這解法一的時間復雜度很大啊，你能優化一下嗎，稍加思索，我們想到，如果考慮使用哈希表空間換時間，則可以降低時間復雜度，我們可以使用哈希表存盤陣列中元素出現的次數，當某個元素的出現次數超過一半時，回傳該元素，于是得到演算法：

演算法

1.初始化存盤陣列元素及其出現次數的哈希表map1，鍵為元素值，值為該元素在陣列中的出現次數；
2.遍歷陣列元素，將被遍歷陣列元素的哈希值加一；
3.若該元素在陣列中的出現次數超過陣列元素數的一半，回傳該元素，

代碼

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {
 4         unordered_map<int, int> map1;//存盤陣列元素值及出現次數的哈希表
 5         for(int i = 0; i < nums.size(); i++)//遍歷陣列元素
 6         {
 7             map1[nums[i]]++;//該元素出現次數加一
 8             if(map1[nums[i]] > nums.size()/2)//若該元素出現此處超過一半
 9             {
10                 return nums[i];//回傳該元素
11             }
12         }
13         return 0;//為了能通過編譯
14     }
15 };

復雜度分析

時間復雜度： O(m)，遍歷陣列元素的時間開銷，
空間復雜度： O(m)，哈希表的空間消耗，

解法三 隨機演算法

解題思路

這時候面試官又說了，你這解法二空間復雜度連解法一都不如，再想想有沒有更好的解法，
手扶下巴，眉頭一皺，我們又想到，由于多數元素是指在陣列中出現次數大于?n/2? 的元素，因此如果我們隨機選取陣列中的一個元素，那么將有超過1/2的概率選到該多數元素，于是可以使用這種演算法：

演算法

1.在陣列中隨機挑選一個元素；
2.遍歷陣列統計該元素出現次數，若超過陣列元素數的一半，回傳該元素，否則重新隨機挑選一個元素，

代碼

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {
 4         int m = nums.size();//計算陣列元素數
 5         srand(time(NULL));//設定亂數種子
 6         int n;//存盤亂數
 7         int count = 0;//初始化以亂數為下標的元素的出現次數為0
 8         while(count<=m/2){//當以亂數為下標的元素出現次數未超過陣列元素數的一般
 9             n = rand()%m;//獲取一個亂數
10             count = 0;//初始化以亂數為下標的元素出現次數為0
11             for(int num : nums) if(num == nums[n]) ++count;//統計以亂數為下標的元素出現次數
12         }
13         return nums[n];//若以該亂數為下標的元素出現次數超過陣列元素數的一半，回傳以該亂數為下標的元素
14     }
15 };

復雜度分析

時間復雜度： O(m)，理論上最壞情況下復雜度為O(∞)，但實際上由于多數元素出現次數超過陣列元素數的一半，平均情況下只需要兩次就能選出多數元素，主要的時間開銷是統計出現次數，其時間復雜度為O(m)，
空間復雜度： O(1)，只需常數個額外空間，

解法四 摩爾投票法

解題思路

面試官覺得你這解法很有意思，然后又問，那要我就是非酋呢，那豈不是無限回圈了，有沒有更好的辦法，
這下可讓人犯了難，有什么更好的辦法既能時間最優又能空間最優呢？
考慮這樣一個場景，一群人打擂臺，人群中分為不同的幫派，挨個上臺比武，留在臺上的幫派為擂主幫派，如果上臺的人不是自己幫派的人，則將其干掉，代價是損失一個幫派成員；如果上臺的人是自己幫派的人，則將其留下，則當所有人都參與完比武后，留在臺上的必然可以是人數超過比武人數一半的幫派，而在本題中，多數元素出現次數超過陣列元素數的一半，也即，其他所有元素加起來都沒多數元素多，如果我們記多數元素的值為1，其他元素的值為0，將陣列中所有元素值相加，結果必然大于0，于是我們可以設計這樣一種演算法：

演算法

1.初始化候選答案ans為nums[0],初始化數值計算結果count為0；
2.遍歷陣列若該元素與備選答案相等，count加一，否則減一；
3.若count減為零，更換備選答案ans為當前元素，重置count為1，繼續遍歷后續元素，
遍歷完成后回傳最終的ans即為多數元素，

代碼

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {
 4         int ans = nums[0];//初始化候選答案為nums[0]
 5         int count = 0;//初始化數值計算結果為0
 6         for(auto num : nums){//遍歷陣列
 7             if(num==ans) ++count;//若該元素與備選答案相同，則count加一
 8             else{//否則減一
 9                 --count;
10                 if(count==0){//若count減為0
11                     ans = num;//更換備選答案為當前元素
12                     ++count;//重置count為1
13                 }
14             }
15         }
16         return ans;//回傳答案
17     }
18 };

復雜度分析

時間復雜度： O(m)，只需要對陣列進行一次遍歷即可
空間復雜度： O(1)，只需常數個額外空間，

Tips:

由于題目明確說明給定的陣列中總是存在多數元素，因此本題不用考慮陣列不存在多數元素的情況，若未做說明，需要像解法三那樣，在選出ans以后再進行一次統計，驗證該元素是否是多數元素，若果是，回傳之；如果不是，回傳不存在多數元素，時間復雜度和空間空間復雜度不變，

更多知識內容分享：

力扣個人主頁https://leetcode-cn.com/profile/articles/
CSDN個人主頁https://blog.csdn.net/qq_39255924
牛客個人主頁https://blog.nowcoder.net/newcoderthewarrior

可可愛愛的蕾姆鎮

標籤：C++

上一篇：Python基礎（二十）：pip命令大全

下一篇：返回列表