前言
哈喽，大家好，我是一条
糊涂算法，难得糊涂
昨天面试字节，切实感受到了刷算法带来的提升
生命不息，刷题不止
Question
169. 多数元素
难度：简单
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：[3,2,3] 输出：3
示例2:
输入：[2,2,1,1,1,2,2] 输出：2
进阶：
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
Solution
一条开始采用的
hashmap计数法，不用想，结果肯定超时了足足
17ms
HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])){ map.put(nums[i],map.get(nums[i])+1); if (map.get(nums[i])>nums.length/2){ return nums[i]; } }else { map.put(nums[i],1); } } return nums[0];
后来发现有个方法叫摩尔投票
摩尔投票法
核心就是对拼消耗。
玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。
那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。
最后能剩下的必定是自己人。
定义一个计数器count=1，多数元素cur=numsp[0]
如果当前数字和多数元素相同，count++
如果当前数字和多数元素不同,count--
如果count==0，更换cur的值
理解了摩尔投票法后，良心推荐一道进阶的题目：求众数Ⅱ
Code
所有
leetcode代码已同步至github欢迎
star
class Solution { public int majorityElement(int[] nums) { int cand_num = nums[0], count = 1; for (int i = 1; i < nums.length; ++i) { if (cand_num == nums[i]) { ++count; }else if (--count == 0) { cand_num = nums[i]; count = 1; } } return cand_num; } }
Result
复杂度分析
- 时间复杂度：O(N)
🌈寻宝
⭐今天是坚持刷题更文的第11/100天
⭐各位的点赞、关注、收藏、评论、订阅就是一条创作的最大动力
⭐更多算法题欢迎关注专栏《leetcode》
为了回馈各位粉丝，礼尚往来，给大家准备了一条多年积累下来的优质资源，包括 学习视频、面试资料、珍藏电子书等
怎么领取请大家自己找，寻宝游戏现在开始。
找不到可以评论留言，一条就会注意到你。
如果还不行，请私信我。
