[哈希表][摩尔投票法]leetcode169：求众数(easy)

众数(easy)"/>

[哈希表][摩尔投票法]leetcode169：求众数(easy)

题目：

题解：

解法1：哈希表，哈希表用来建立元素和该元素频率之间的映射，然后返回频率大于n/2的元素。

---

解法2：排序，先将数组进行排序，由于本题隐含条件就是数组中一定存在众数，所以众数在排序后的数组中，必定位于下标[n/2]处。

---

解法3：摩尔投票法，摩尔投票法遇到相同的数，就投一票，遇到不同的数，就减一票，最后还存在票的数就是众数。原因：由于众数的出现次数大于数组长度的一半，所以在使用摩尔投票法的时候，众数的个数减去其他数的个数时，众数还会有剩余的。

代码如下：

class Solution {
public://解法1：哈希表int majorityElement_1(vector<int>& nums) {unordered_map<int,int> record;//元素->频率for(int i=0;i<nums.size();++i){record[nums[i]]++;if(record[nums[i]]>nums.size()/2)return nums[i];}return -1;}//解法2：排序//由于众数出现的频率大于n/2,所以在排序之后众数必存在于下标[n/2]处(本题默认数组中是一定存在众数的，所以返回下标[n/2]可行)int majorityElement_2(vector<int>& nums) {sort(nums.begin(),nums.end());return nums[nums.size()/2];}//解法3：摩尔投票法//摩尔投票法，遇到相同的数，就投一票，遇到不同的数，就减一票，最后还存在票的数就是众数int majorityElement_3(vector<int>& nums){int count=0,result=-1;for(const auto& num:nums){if(count==0)result=num;if(num==result)++count;else --count;}return result;}
};