剑指 Offer 39. 数组中出现次数超过一半的数字
2021/8/10 23:38:07
本文主要是介绍剑指 Offer 39. 数组中出现次数超过一半的数字,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
剑指 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)
这篇关于剑指 Offer 39. 数组中出现次数超过一半的数字的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-15Spring Boot项目开发教程:快速入门与实战指南
- 2024-09-15单点登录实战:入门级指南与实操详解
- 2024-09-15登录校验实战:从零构建安全登录系统
- 2024-09-15Java知识库系统学习:从零开始的编程之旅
- 2024-09-15JAVA知识库系统学习:从零基础到入门的全面指南
- 2024-09-15Java主流技术学习:从入门到进阶的实用指南
- 2024-09-15JAVA主流技术学习:从入门到提升
- 2024-09-15Java主流技术学习:从入门到上手的实践指南
- 2024-09-15实战编程技巧:从基础概念到实际应用
- 2024-09-15掌握JAVA主流框架学习:从入门到实践