229 Majority Element II 求众数 II
2024-08-29 05:57:40
给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 你的算法应该在O(1)空间中以线性时间运行。
详见：https://leetcode.com/problems/majority-element-ii/description/
摩尔投票法 Moore Voting
Java实现：
class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> res=new ArrayList<Integer>();
if(nums==null||nums.length==0){
return res;
}
int a=nums[0],cnta=0;
int b=nums[0],cntb=0;
for (int num : nums) {
if (num == a) {
++cnta;
}else if(num == b) {
++cntb;
}else if(cnta == 0) {
a = num;
cnta=1;
}else if(cntb == 0) {
b = num;
cntb=1;
}else{
--cnta;
--cntb;
}
}
cnta=0;
cntb=0;
for(int num:nums){
if(num==a){
++cnta;
}else if(num==b){
++cntb;
}
}
if(cnta>nums.length/3){
res.add(a);
}
if(cntb>nums.length/3){
res.add(b);
}
return res;
}
}
C++实现：
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> res;
int m = 0, n = 0, cm = 0, cn = 0;
for (auto &a : nums)
{
if (a == m)
{
++cm;
}
else if (a ==n)
{
++cn;
}
else if (cm == 0)
{
m = a, cm = 1;
}
else if (cn == 0)
{
n = a, cn = 1;
}
else
{
--cm, --cn;
}
}
cm = cn = 0;
for (auto &a : nums)
{
if (a == m)
{
++cm;
}
else if (a == n)
{
++cn;
}
}
if (cm > nums.size() / 3)
{
res.push_back(m);
}
if (cn > nums.size() / 3)
{
res.push_back(n);
}
return res;
}
};
参考：https://www.cnblogs.com/grandyang/p/4606822.html
最新文章
- linux c++编译问题和虚拟机网络通信
- UISearchBar控件-让我们来搞定！（转）
- QQ空间HD(1)-UIPopoverController基本使用
- mysql 删除重复数据保留只保留一条
- LiveView 0.8 RC1 could boot evidence files acquired from Win10 64bit
- oradmin相关用法
- 2136 Largest prime factor（打表）
- 学习CSS记录：CSS文件引入到HTML中
- win10 uwp 绑定密码
- 控制公司 Controlling Companies
- 简单的纯js三级联动
- Java复习总结——String
- Python课程第三天作业
- 学习windows编程 day3 之窗口绘画一：点线绘制
- CF875D High Cry
- nslookup dig iptables,sudoer,jenkins
- javascript 获取html元素的三种方法
- ECLIPSE修改xml配置文件TOMCAT不生效的解决
- VScode之JavaScript Snippet Pack
- SpringMVC源码剖析（五)-消息转换器HttpMessageConverter
热门文章
- MySQL基础笔记（三） 复杂查询
- 获取Windows用户所有的账户名
- JAVA设计模式（01）：创建型-工厂模式【工厂方法模式】(Factory Method)
- java8--集合(疯狂java讲义3复习笔记)
- Tomcat 安装错误
- TCP Operational Overview and the TCP Finite State Machine (FSM) http://tcpipguide.com/free/t_TCPOperationalOverviewandtheTCPFiniteStateMachineF.htm
- EJB3.0
- JavaScript语言基础4
- XMU C语言程序设计实践（1）
- mongo11---Access control is not enabled for the database