腾讯50题精选
题目描述解题思路以及运用知识点Leetcode运行代码
题目描述
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3] 输出: 3 示例 2:
输入: [2,2,1,1,1,2,2]
解题思路以及运用知识点
本题乍看简单，但是如果不仔细审题容易将题目看错。很显然。本题的关键点在于对于众数的定义。本题中众数是指出现次数大于[n/2]的元素，定义和传统数学中的众数不同。 从定义中，我们至少可以得到两个基本信息：1、大于[n/2]的元素为众数，也就是众数只有一个。2、由于众数个数大于[n/2],那么如果将 数组中的所有数排序，那么最中间的数，一定就是众数。
Leetcode运行代码
class Solution {
public:
static bool
cmp(const int
&a
, const int
&b
)
{
return a
< b
;
}
int
majorityElement(vector
<int
>& nums
) {
sort(nums
.begin(), nums
.end(), cmp
);
return nums
[nums
.size()/2];
}
};
解法二：因为众数的个数总是大于总元素的一半。那么如果从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，总能找到最多的那个；
class Solution {
public:
int
majorityElement(vector
<int
>& nums
) {
int res
=nums
[0];
int count
=1;
for(int i
=1;i
<nums
.size();i
++)
{
if(res
==nums
[i
])
count
++;
else
{
count
--;
if(count
==0)
res
=nums
[i
+1];
}
}
return res
;
}
};
如果有帮助，欢迎关注。一起学习快乐！
