leetcode 229 Majority Element II
2024-03-31 21:42:25
这题用到的基本算法是Boyer–Moore majority vote algorithm
wiki里有示例代码
1 import java.util.*;
2 public class MajorityVote {
3 public int majorityElement(int[] num) {
4 int n = num.length;
5 int candidate = num[0], counter = 0;
6 for (int i : num) {
7 if (counter == 0) {
8 candidate = i;
9 counter = 1;
10 } else {
11 if (i == candidate) {
12 counter++;
13 } else {
14 counter--;
15 }
16 }
17 }
18
19 counter = 0;
20 for (int i : num) {
21 if (i == candidate) counter++;
22 }
23 if (counter < (n + 1) / 2) return -1;
24 return candidate;
25
26 }
27 public static void main(String[] args) {
28 MajorityVote s = new MajorityVote();
29 System.out.format("%d\n", s.majorityElement(new int[] {1, 2, 3}));
30 System.out.format("%d\n", s.majorityElement(new int[] {2, 2, 3}));
31 }
32 }
基本想法是这样的：在数组中数目超过 n /2的元素至多有一个，所以遍历过程中只有一个候选元素
我们假设有某个元素满足这种要求：若他均匀分布，至少每间隔一个出现一次；而且还不够，至少在某处多出现了一次
现在想一下不均匀的情况：如果该元素间隔了很长没出现，则至少在这个长间隔的前面或后面出现密集区域。
vector<int> majorityElement(vector<int>& nums) {
if(nums.empty())
return vector<int>();
if(nums.size() == 1){
return vector<int>({nums[0]});
}
vector<pair<int, int>> candidates;
for(auto num : nums){
if(candidates.size() < 1){
candidates.emplace_back(num, 2);
}
else if(candidates.size() < 2){
if(num != candidates[0].first)
candidates.emplace_back(num, 2);
else
candidates[0].second++;
}
else{
if(num == candidates[0].first){
candidates[0].second++;
candidates[1].second--;
}
else if(num == candidates[1].first){
candidates[1].second++;
candidates[0].second--;
}
else{
candidates[0].second--;
candidates[1].second--;
int ind = candidates[0].second < candidates[1].second ? 0 : 1;
if(candidates[ind].second <= 0){
candidates[ind].first = num;
candidates[ind].second = 2;
}
}
}
}
for(auto& candidate : candidates){
candidate.second = 0;
}
for(auto num : nums){
for(auto& candidate : candidates){
if(num == candidate.first)
candidate.second++;
}
}
vector<int> result;
for(auto candidate:candidates){
if(candidate.second > nums.size() / 3)
result.push_back(candidate.first);
}
return result;
}
最新文章
- Hibernate创建hqll时报错
- Unity Scripting Tutorials 要点记录
- acdream 1683 村民的怪癖(KMP，经典变形)
- 【转】java静态代码块和构造方法执行顺序
- html5+css3中的background: -moz-linear-gradient 用法 (转载)
- jquery ajax验证用户名是否存在（后台spring mvc）
- 必须掌握的JavaScript基本知识
- angular4.0配置本机IP访问项目
- Hadoop2.x 体系结构和源码编译
- 文件下载的ie11兼容性优化
- 452. Minimum Number of Arrows to Burst Balloons
- jQuery validator plugin之Methods
- webapi Filter
- vivado SDK之找不到"platform.h"
- java中length与length()
- Java-Runoob-高级教程-实例-数组：13. Java 实例 – 数组交集
- python爬取酒店信息练习
- Qt程序修改Ubuntu系统时间
- 解决IDEA 中git 无法自动push 提交问题 Push failed: Failed with error: Could not read from remote repository.
- php session阻塞页面分析及优化 （session_write_close session_commit使用）