众数(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;}
};
更多推荐
[哈希表][摩尔投票法]leetcode169:求众数(easy)
发布评论