leetcode_169_求众数

本文主要是介绍leetcode_169_求众数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

---

class Solution {
public:int majorityElement(vector<int>& nums) {if(nums.size()==1)return nums[0];map<int,int> tables;for(int i=0;i<nums.size();i++){if(tables.count(nums[i])){tables[nums[i]]++;if(tables[nums[i]]>nums.size()/2)return nums[i];}else{tables[nums[i]]=1;}}}
};

这种解法是使用一个hash表map<>，键用来存放数组的元素，键对应的值存放元素出现的次数。遍历整个数组，查找它在hash表中是否出现，如果出现将出现次数加1，如果没有出现，将它插入hash表中，并设置它的出现次数为1。每次遍历到一个元素，判断它的出现次数是否超过了数组长度的一半，要是超过了就返回该元素。时间复杂度是O(n)，空间复杂度是O(n)。

class Solution {
public:int majorityElement(vector<int>& nums) {sort(nums.begin(),nums.end());return nums[nums.size()/2];}
};

对数组进行排序，那么出现次数超过一半的元素必定是数组中的中间元素，返回这个元素即可。时间复杂度是O(nlogn)，空间复杂度是O(1)。

int majorityElement(vector<int>& nums) {int count=0;int result=nums[0];for(int i=0;i<nums.size();i++){if(count==0||nums[i]==result){count++;result=nums[i];}elsecount--;}return result;}

每找出两个不同的element，就成对删除即count--，最终剩下的一定就是所求的。时间复杂度：O(n) 空间复杂度为O(1)。

 

 

这篇关于leetcode_169_求众数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---