每日一题 - 剑指 Offer 39. 数组中出现次数超过一半的数字
2024-08-25 07:05:39
题目信息
时间: 2019-06-29
题目链接:Leetcode
tag: 数组 哈希表
难易程度:简单
题目描述:
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
假设数组是非空的,并且给定的数组总是存在多数元素。
示例:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
提示
1 <= 数组长度 <= 50000
解题思路
本题难点
如何实现查找数组中的众数的最优解,时间复杂度和空间复杂度最小。
具体思路
摩尔投票法:
- 票数和:由于众数出现的次数超过数组长度的一半;若记 众数 的票数为 +1 ,非众数 的票数为 −1 ,则一定有所有数字的票数和 > 0。
- 票数正负抵消: 设数组
nums
中的众数为 x ,数组长度为 n 。若 nums 的前 a 个数字的 票数和 =0 ,则 数组后 (n−a) 个数字的 票数和一定仍 > 0 (即后 (n−a) 个数字的 众数仍为 x )。
为构建正负抵消,假设数组首个元素 为众数,遍历统计票数,当发生正负抵消时,剩余数组的众数一定不变 ,这是因为(设真正的众数为 x ):
- 当 n1=x : 抵消的所有数字中,有一半是众数 x 。
- 当 n1≠x : 抵消的所有数字中,少于或等于一半是众数 x 。
利用此特性,每轮假设都可以 缩小剩余数组区间 。当遍历完成时,最后一轮假设的数字即为众数(由于众数超过一半,最后一轮的票数和必为正数)。
代码
class Solution {
public int majorityElement(int[] nums) {
//票数统计 count=0
int count = 0;
//众数 x
int x = 0;
//遍历数组 nums 中的每个数字 num
for(int num :nums){
//当 票数 count 等于 0 ,则假设 当前数字 num 为 众数 x ;
if(count == 0){
x = num;
}
//当 num=x 时,票数 count 自增 1 ;否则,票数 count 自减 1
if(num == x){
count++;
}else{
count--;
}
}
return x;
}
}
复杂度分析:
- 时间复杂度 O(N) :数组长度为N ,遍历数组花费的时间。
- 空间复杂度 O(1) : 只开辟了一个空间用于保存众数。
其他优秀解答
解题思路
哈希表统计法:遍历数组 nums,用 HashMap 统计各数字的数量,最终超过数组长度一半的数字则为众数。此方法时间和空间复杂度均为 O(N)。
代码
class Solution {
public int majorityElement(int[] nums) {
HashMap<Integer,Integer> map = new HashMap<>();
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
if(map.get(num)>(nums.length/2)){
return num;
}
}
return -1;
}
}
最新文章
- 分辨率、DPI、PPI和屏幕尺寸,你都知道是啥么?
- Elasticsearch 5.0
- IE6完美解决fixed方法
- Lintcode--005(最长公共子序列)
- Flask-Request对象属性
- redis------del命令
- redis学习(2)--- Redis概述
- Cocos2D将v1.0的tileMap游戏转换到v3.4中一例(七)
- 【ABP框架系列学习】模块系统(4)
- 练习七 Procedure中使用DDL
- Git与GitHub的基本使用
- 关于在搜索栏的一些小bug
- vue-4-Class 与 Style 绑定
- Gradle 实战(1)—— 配置环境变量
- CSS3新增特性详解(一)
- 类的const和非const成员函数的重载
- C - The C Answer (2nd Edition) - Exercise 1-2
- Linux下libsvm的安装及简单练习
- 分享一个PC端六格密码输入框写法
- 【左偏树】BZOJ2809-[APIO2012]dispatching
热门文章
- Java实现 基础算法 水仙花数
- Java实现构造无向图的欧拉回路( The Necklace)
- 2018年全国多校算法寒假训练营练习比赛(第二场)H-了断局
- HDU-3033 I love sneakers! 题解
- 线性表 &; 散列表
- [ARC101B]Median of Medians
- CDN百科第四讲 | 如何优雅地在云上“摆摊”——做直播带货,你不得不关注的技术
- TensorFlow从0到1之TensorFlow实现简单线性回归(15)
- os.remove() 删除文件
- fiddler下载安装