剑指 Offer 39. 数组中出现次数超过一半的数字
2024-09-03 06:20:26
剑指 Offer 39. 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
限制:
1 <= 数组长度 <= 50000
一、摩尔算法
具体摩尔算法,我借鉴一下大神的解释更好理解点。
为什么答案能写那么长呢。。。核心就是对拼消耗。玩一个诸侯争霸的游戏,假设你方人口超过总人口一半以上,并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。那就大混战呗,最差所有人都联合起来对付你(对应你每次选择作为计数器的数都是众数),或者其他国家也会相互攻击(会选择其他数作为计数器的数),但是只要你们不要内斗,最后肯定你赢。最后能剩下的必定是自己人。
class Solution {
public int majorityElement(int[] nums) {
int vote = 0, x = 0;
for (int num : nums) {
if (vote == 0) x =num;
vote += num == x ? 1 : -1;
}
return x;
}
/*
x=num=1
vote=1
x = 2
vote = 0
x =3 vote=1
vote = 0
x = num =2 vote =1
*/
}
除了这个,由于题目要求给定的数组总是存在多数元素,所以需要加入“验证环节”,所以借鉴了K神的思路,遍历数组统计x的量,如果大于num.length/2,则x是众数,否则反正。
class Solution {
public int majorityElement(int[] nums) {
int vote = 0, x = 0, count = 0;
for (int num : nums) {
if (vote == 0) x =num;
vote += num == x ? 1 : -1;
}
for (int num : nums)
if (num == x) count++;
return count > nums.length/2 ? x : 0;
}
}
二、哈希
class Solution {
/*
用HashMap统计num的数量,即可找出众数
*/
public Map<Integer,Integer> map(int[] nums) {
Map<Integer,Integer> map = new HashMap<Integer, Integer>();
for (int num : nums) {
if (!map.containsKey(num)) {
map.put(num, 1);
} else {
map.put(num,map.get(num) + 1);
}
}
return map;
}
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = map(nums);
Map.Entry<Integer,Integer> majorityElement = null;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (majorityElement == null || entry.getValue() > majorityElement.getValue()) {
majorityElement = entry;
}
}
return majorityElement.getKey();
}
}
三、数组排序
class Solution {
/*
用数组nums进行排序
*/
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
参考链接:
1)https://www.zhihu.com/question/49973163/answer/617122734
2)剑指 Offer 39. 数组中出现次数超过一半的数字(摩尔投票法,清晰图解) - 数组中出现次数超过一半的数字 - 力扣(LeetCode) (leetcode-cn.com)
最新文章
- Windows下虚拟机安装Ubuntu15.10 Destop简易操作过程
- 小白Linux入门 二
- IE6不支持min-height或max-width等完美解决方法
- php设计模式 Proxy (代理模式)
- CSS成长之路----知识点篇
- PIC12F629帮我用C语言写个程序,控制三个LED亮灭
- 菜鸟开始学习SSDT HOOK((附带源码)
- ORM 框架
- apache开源项目 --Struts
- Jordan Lecture Note-11: 典型相关分析(Canonical Correlation Analysis, CCA).
- linux shell 常用基本语法
- HTML5要点(四)对象全整理
- Redis未授权访问缺陷让服务器沦为肉鸡
- UITableView刷新局部
- CSS学习笔记1:基础知识
- 机器学习(九)隐马尔可夫模型HMM
- CentOS 7的安装详解
- JVM内存模型一
- asp.net 导出 Excel 身份证格式显示格式问题
- iOS开源项目周报0223
热门文章
- Visual Studio Code 和Visual Studio插件收集(持续更新)
- 关于Word转Markdown的工具Writage安装及使用
- 台达PLC开发笔记(二):台达PLC设置主机通讯参数为RTU并成功通讯
- Cobra框架使用手册
- 『心善渊』Selenium3.0基础 — 22、使用浏览器加载项配置实现用户免登陆
- 每日英语——the rest of my life
- ESP32低功耗模式
- Python单元测试框架unittest之断言(assert)
- 高校表白App-团队冲刺第五天
- 论文阅读:Visual-Inertial Localization With Prior LiDAR Map Constraints