【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以后再进行一次统计，验证该元素是否是多数元素，若果是，回传之；如果不是，回传不存在多数元素，时间复杂度和空间空间复杂度不变，