题目描述:
给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
解题思路1:
先排序,中间的那个数一定是众数,时间复杂度为O(nlogn);
代码1:
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums[nums.size()/2];
}
};
解题思路2:
摩尔投票法,时间复制度O(n);
因为数组中一定存在众数,故众数的个数一定比非众数的个数多,即遇到众数加1,否则减1;
代码2:
class Solution {
public:
int majorityElement(vector<int>& nums) {
int count = 0;
int moore = 0;
for(int num : nums)
{
if(count == 0)
moore = num;
if(moore == num)
count++;
else
count--;
}
return moore;
}
};
解题思路3:
使用map容器,将数组中的值作为key值,出现的次数作为value值,找出其中众数,时间复杂度为nlog(n);
代码3:
class Solution {
public:
int majorityElement(vector<int>& nums) {
map<int, int> majorityMap;
int max=0,maxKey=0;
for(int num : nums)
{
auto it = majorityMap.find(num);
if(it == majorityMap.end())
majorityMap.insert(pair<int, int>(num, 1));
else
it->second++;
}
for(auto it = majorityMap.begin(); it != majorityMap.end(); ++it)
{
if(max < it->second)
{
max = it->second;
maxKey = it->first;
}
}
return maxKey;
}
};
补充知识:STL map关联容器
Map是STL的一个关联容器,它提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值)的数据 处理能力,由于这个特性,它完成有可能在我们处理一对一数据的时候,在编程上提供快速通道。这里说下map内部数据的组织,map内部自建一颗红黑树(一 种非严格意义上的平衡二叉树),这颗树具有对数据自动排序的功能,所以在map内部所有的数据都是有序的,后边我们会见识到有序的好处。
(1)、map特点:
map是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很小,除了那个操作节点,对其他的节点都没有什么影响。对于迭代器来说,可以修改实值,而不能修改key。
自动建立Key-value的对应。key 和 value可以是任意你需要的类型。
根据key值快速查找记录,查找的复杂度基本是Log(N)
(2)、基本用法:
1、构造map:map<int, int> mmap;
2、插入数据:以下三种方式等价
mmap.insert(pair<int, int>(1,1));
mmap.insert(map<int, int>::value_type(1,1));
mmap[1] = 1;
3、数据遍历:
for(auto it = mmap.begin(); it != mmap.end(); ++it)
cout << it->first << " : " << it->second << endl;
4、按key查找:
auto it = mmap.find(1);//返回key值为1的迭代器
5、删除:
mmap.erase(it);
mmap.erase(1);
mmap.erase(mmap.begin(), mmap.end());
网友评论