本文主要是介绍C++:主要元素,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
C++:主要元素
问题描述
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组,找出其中的主要元素。若没有,返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
示例 1:
输入:[1,2,5,9,5,9,5,5,5]
输出:5
示例 2:
输入:[3,2]
输出:-1
示例 3:
输入:[2,2,1,1,1,2,2]
输出:2
分析
- 最容易想到的一个方法是使用Hash表进行计数,依次遍历并判断当前数出现的次数是否大于长度的一半,该方法时间复杂度为O(n),空间复杂度为O(n)
- 注意到主元是超过一半的元素,因此可以考虑使用moor投票算法先找到出现最多的数,然后再统计其长度。
实现
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int Moore(vector<int> &nums);
int Hash(vector<int> &nums);
int main()
{
vector<int> nums = {3,3,4};
//return Hash(nums);
return Moore(nums);
system("pause");
}
int Hash(vector<int>& nums)
{
unordered_map<int,int> cnt;
for(auto& num:nums)
{
if((++cnt[num]) > (nums.size()/2))
return num;
}
return -1;
}
int Moore(vector<int>& nums)
{
int major = -1, cnt = 0;
for(auto& num:nums)
{
if(cnt == 0)
{
major = num;
cnt = 1;
}
else if(major == num)
cnt++;
else
cnt--;
}
for(auto& num:nums)
{
if(major == num)
cnt++;
}
if(cnt > nums.size()/2)
return major;
else
return -1;
}
这篇关于C++:主要元素的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!