当前位置：首页 > news >正文

【LeetCode】剑指 Offer 39. 数组中出现次数超过一半的数字 p205 -- Java Version

news 来源：原创 2024/5/10 23:58:51

题目链接：https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/

1. 题目介绍（39. 数组中出现次数超过一半的数字）

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

【测试用例】：
示例1：

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

【条件约束】：

提示：

1 <= 数组长度 <= 50000

【相关题目】：

注意：本题与主站 169. 多数元素题目相同。

2. 题解

2.1 暴力穷举 – O(n²)

时间复杂度O(n²)，空间复杂度O(n)

【解题思路】：
对于排序数组，我们可以很容易统计出每个数字出现的次数，可参考剑指 Offer 53 - I. 在排序数组中查找数字 I ，然后再对次数进行判断，看是哪个数字出现的次数超过了数组长度的一半。
……
【实现策略】：

对输入数组 nums 使用 sort() 方法进行升序排序；
【sort()方法详解】：详述Java中sort排序函数
定义一个 HashMap 用来记录每个数字在数组中出现的次数，数组中数组为键，出现的次数为值；
【注意点】：HashMap 的键虽然不能重复，但是如果是有重复键的键值对要加入，那么 新值会覆盖掉旧值，切记！
双循环穷举，当然下面为了提高效率，同时防止重复键值对被覆盖，通过每次循环中把 j 赋值给 i 的操作，这样就保证了内循环结束后，i 位于当前重复数字的末尾，而由于循环结束，i++ 的原因，这样就相当于间接的移动 i 到了下一个非重复数组数字的位置，然后进行下一个数字重复次数的统计；（这里的双循环穷举，可以改为 一次遍历 + 二分查找（找左右边界） 的方式，进一步提高统计效率）
最后，遍历 HashMap，找出次数超过数组一半的数字并返回。

class Solution {public int majorityElement(int[] nums) {// 对数组进行排序Arrays.sort(nums);// 遍历数组// 定义map用来记录每个数字在数组中出现的次数HashMap<Integer,Integer> map = new HashMap<>();int n = 0;for(int i = 0; i < nums.length; i++){for (int j = i; j < nums.length; j++){if (nums[j] == nums[i]) {n++;i = j; // 将i移到下一个数的位置} }map.put(nums[i],n);n = 0;}// 遍历map，找出超过一半数组长度的数字for(Map.Entry<Integer,Integer> entry : map.entrySet()){if (entry.getValue() > nums.length/2) return entry.getKey();}return 0;}
}

在这里插入图片描述
代码简化：

【实现策略】：
看了题解，意识到自己傻冒了，忘了 HashMap 中有 containsKey() 方法了，那么完全可以直接一次遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 ，根本不用双循环，一个一个对比，直接单次循环， containsKey(下一个数字) ，有就++，没有就移动到下一个就完了，此方法时间和空间复杂度均为 O(n) 。

一次遍历，在遍历的过程中将数组数字存入 HashMap ；
判断 HashMap 的键是否已有当前数字，有就加1，没有就下一个。

……
但是不知道为啥，这样好慢，比没简化的代码要慢的多，估计应该是力扣的测试用例设置的不太好。

class Solution {public int majorityElement(int[] nums) {// 遍历数组// 定义map用来记录每个数字在数组中出现的次数HashMap<Integer,Integer> map = new HashMap<>();for(int i = 0; i < nums.length; i++){if (!map.containsKey(nums[i])) map.put(nums[i],1);else map.put(nums[i], map.get(nums[i])+1);}// 遍历map，找出超过一半数组长度的数字for(Map.Entry<Integer,Integer> entry : map.entrySet()){if (entry.getValue() > nums.length/2) return entry.getKey();}return 0;}
}

在这里插入图片描述

2.2 数组排序法 – O(nlogn)

时间复杂度O(nlogn)，空间复杂度O(1)

【解题思路】：
将数组 nums 排序，数组中点的元素一定为众数。
根据题目所出的数组特性：数组中有一个数字出现的次数超过了数组长度的一半，那么如果对这个数组进行排序，排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字。
……
【实现策略】：
根据上面的思路，代码就变的异常的轻松加愉快：

排序
返回数组的中点数字

……
当然如果返回值一变，要求返回该数字的重复次数，这个方法就趴菜了，不过题目摇身一变就变成了剑指 Offer 53 - I. 在排序数组中查找数字 I ，可用 2.1 中的方法解决。

class Solution {public int majorityElement(int[] nums) {// 对数组进行排序Arrays.sort(nums);// 遍历数组return nums[nums.length/2];}
}

在这里插入图片描述

2.3 摩尔投票法（原书题解2） – O(n)

时间复杂度O(n)，空间复杂度O(1)

【解题思路】：
核心理念为 票数正负抵消，因为题目中明确的指出了，要返回的数字是在数组中出现次数超过一半的数字，那么通过正负抵消，最后能留下的一定是该数字。
推论一：若记众数的票数为 +1，非众数 的票数为 -1，则一定有所有数字的 票数和 >0 ；
推论二：若数组的前 a 个数字的 票数和 =0 ，则数组剩余 (n−a) 个数字的票数和一定仍 >0 ，即后 (n−a) 个数字的 众数仍为 x 。

……
【实现策略】：

定义 x 存储众数（候选人），定义票数 votes；
一次遍历，判断当前票是否是给当前候选人的，如果是则加1，如果不是则减1，当候选人的票数为0时，则更换新的候选人。

……
【唠叨两句】：
原书题解1 采用了快排思想的排序方法 Partition() ，一直到 Partition() 方法随机到中点，即，将比中点数小的数字移到数组的左边，比中点数大的数组移到数组的右边。此方法可以，但没必要，除非题目要求不能使用库函数，不然感觉倒是没必要自己写排序，

class Solution {public int majorityElement(int[] nums) {int x = 0, votes = 0, count = 0;for(int num : nums){if(votes == 0) x = num;votes += num == x ? 1 : -1;}// 验证 x 是否为众数for(int num : nums)if(num == x) count++;return count > nums.length / 2 ? x : 0; // 当无众数时返回 0}
}

在这里插入图片描述

3. 参考资料

[1] 剑指 Offer 39. 数组中出现次数超过一半的数字（摩尔投票法，清晰图解）
[2] Java遍历Map的几种方法
[3] 【Java】剑指offer(53-1) 数字在排序数组中出现的次数

鸿蒙开发接口Ability框架：【@ohos.application.Want (Want)】

Want Want模块提供系统的基本通信组件的能力。说明： 本模块首批接口从API version 8 开始支持。后续版本的新增接口，采用上角标单独标记接口的起始版本。导入模块 import Want from ohos.application.Want; 开发前请熟悉鸿蒙开发指导文档&#xff1…...

编程日记 2024/5/10 22:40:34

git对远程和本地分支进行重命名

要同时对Git的远程和本地分支进行重命名，你需要分几个步骤操作： 重命名本地分支切换到其他分支：在重命名当前分支之前，确保你不在你想要重命名的那个分支上。你可以通过以下命令切换到另一个分支（比如切换到master分…...

编程日记 2024/5/10 16:45:04

UcOs-III 源码阅读: os_tmr.c

对定时器源文件os_tmr.c进行源码阅读与注释： // 功能：创建、删除、启动、停止、删除、初始化模块、获取定时器剩余时间、获取定时器状态、 // 创建定时器API: OS_TmrCreate // 删除定时器API: OS_TmrDel // 启动定时器API: …...

编程日记 2024/5/10 15:49:21

平衡树的简单替代品

1、STL / gnu_pbds 1、vector<int> 常用，动态空间注意比较慢，远古题数据小才建议使用。支持操作复杂度序列类别随机访问 \(O(1)\)尾部插入删除 \(O(1)\)随机插入删除 \(O(玄学),O(\sqrt{n})\)集合类别none2、set<int> 维护数集的，它的常数真的很奇妙。支持操作…...

编程日记 2024/5/10 11:54:04

黑马苍穹外卖

sky-pojo子模块内容 Entity：实体，通常和数据库中的表对应DTO：数据传输对象，通常用于程序中各层之间传递数据（eg：前端返回的json数据，后端要接收，并且转化为java对象，此时…...

编程日记 2024/5/10 11:05:22

Kubernetes（K8s）的基础概念

目录一、Kubernetes（K8s）概述 1、K8s是什么？ 2、k8s的作用 3、k8s的功能二、k8s的特性 ①弹性伸缩： ②自我修复： ③服务发现和负载均衡： ④自动发布（默认滚动发布模式）和…...

编程日记 2024/5/10 4:43:38

【LeetCode】剑指 Offer 39. 数组中出现次数超过一半的数字 p205 -- Java Version

题目链接：https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/ 1. 题目介绍（39. 数组中出现次数超过一半的数字） 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可…...

编程日记 2024/5/10 23:58:51

es-head插件插入查询以及条件查询（五）

es-head插件插入查询以及条件查询 1.es-head插件页面介绍页面详细介绍 2.es-head查询语句 2.1.查询索引中的全部数据 curl命令交互，采用GET请求语法格式： curl -XGET es地址:9200/索引名/_search?pretty [rootelaticsearch ~]# curl -XGET 192…...

编程日记 2024/5/2 7:22:25

数据挖掘（作业汇总）

目录环境配置实验1 数据作业2 环境配置实验开始前先配置环境以实验室2023安装的版本为例： 1、安装anaconda：（anaconda自带Python,安装了anaconda就不用再安装Python了） 下载并安装 Anaconda3-2022.10-Windows-x86_64.ex…...

编程日记 2024/5/10 18:16:37

基于微信小程序的图书馆选座系统源码

开发环境及工具： 大等于jdk1.8，大于mysql5.5，idea（eclipse），微信开发者工具技术说明： springboot mybatis 小程序代码注释齐全，没有多余代码，适合学习（…...

编程日记 2024/5/10 14:46:25

特斯拉4D成像毫米波雷达与木牛科技早期开源的产品几乎一模一样？

近日，在中欧智能网联汽车协会秘书长林示的组织下，中益基金投资总监王子文考察了全球毫米波雷达领跑者—木牛科技。考察过程中，木牛科技COO王卫向两位详细介绍了木牛科技具备怎样的全球毫米波雷达领跑者的科技硬实力，以及木牛科技…...

编程日记 2024/5/10 1:33:03

[golang gin框架] 10.Gin 商城项目介绍

一.商城项目介绍 1.详细功能介绍图 2.数据库 ER 图需要用到的数据表举例二.MVC架构搭建以及执行流程分析 1.关于 MVC 模式的简单介绍 Gin 不是一个 MVC 的框架，所有的代码都可以写在 main.go 中。当我们的项目比较大的时候， 所有代码写在一个文件里面…...

编程日记 2024/5/10 18:40:54

python@调用系统命令行@os.system@subprocess@标准输入输出@sys.stdin@sys.stdout@input@print

文章目录python调用系统命令行os.system标准输入输出sys.stdinsys.stdoutinputprint概要os.systemdemoswindows命令解释器ComSpecsubprocessrecommended🎈基本用法demos标准输入输出sys.stdininput()sys.stdin.inputinput()交互模式小结sys.stdoutsys.stdout.wirte(…...

编程日记 2024/5/10 5:48:50

15-哈希表

哈希表（Hash table），也称散列表，是一个能够将数值映射而成地址从而进行直接访问的数据结构，通过哈希表我们可以快速、迅捷地访问数据。哈希表原理假设我们拥有一个数x（也称关键值，key&#…...

编程日记 2024/5/10 9:27:58

【超详细文件操作（三）】C语言

作者：日出等日落专栏：C语言只有流过血的手指，才能弹出世间的绝唱。 ——泰戈尔目录 1.文件的随机读写 1.1 fseek函数 1.1.1 下面使用fseek函数 1.2 ftell函数 1.3 rewind函数 …...

编程日记 2024/5/10 23:18:53

【数据分析之道-基础知识(四)】字典

文章目录专栏导读1、字典简介2、字典创建3、字典访问4、字典修改5、字典添加6、字典删除7、字典内置函数专栏导读 ✍ 作者简介：i阿极，CSDN Python领域新星创作者，专注于分享python领域知识。 ✍ 本文录入于《数据分析之道》，本专栏…...

编程日记 2024/5/9 21:57:34

【计组】RAM的深入理解

一、存储机理 RAM的实现逻辑有种，分别是触发器和电容。 SRAM（Static）DRAM（Dynamic）存储方式触发器电容破坏性读出否（触发器具有稳态，能够锁住0或1两种状态）是（电容需要…...

编程日记 2024/5/9 20:48:44

51单片机学习笔记_13 ADC

ADC 使得调节开发板上的电位器时，数码管上能够显示 AD 模块采集电位器的电压值且随之变化。开发板上有三个应用：光敏电阻，热敏电阻，电位器。一般 AD 转换有多个输入，提高使用效率。 ADC 通过地址锁存与译码判断采…...

编程日记 2024/5/10 16:15:10

JVM 常量池

Class文件常量池每个Class文件都会有一个单独的常量池,我们称为Class文件常量池,我们可以用javap命令反汇编Class文件,可以查看java编译器为我们生成的字节码。 CLass文件常量池存下内容： 字面量： 文本字符串(代码中用双引号包裹的字符串部分的值)被…...

编程日记 2024/5/10 23:35:45

Leetcode.1024 视频拼接

题目链接 Leetcode.1024 视频拼接 Rating ： 1746 题目描述你将会获得一系列视频片段，这些片段来自于一项持续时长为 time秒的体育赛事。这些片段可能有所重叠，也可能长度不一。使用数组 clips描述所有的视频片段，其中 clips[i…...

编程日记 2024/5/9 6:50:40

彩色滤镜阵列CFA与Bayer滤镜

彩色滤镜阵列（CFA） 在彩色光电摄影中，可以通过分光，使用三个传感器分别捕获红、绿、蓝三个通道的颜色分量。但为了降低成本，绝大部分成像系统中采用单芯片 CMOS、CCD 传感器结合彩色滤镜阵列(Color Fiter Array&#…...

编程日记 2024/5/6 12:50:34

Unity和GAN实现AI绘画五等分的新娘、国家队02(附源码)

UnityGAN实现AI绘画五等分的新娘、国家队02附源码写在前面源码演示视频部分界面展示使用教程敬请期待其他写在后面写在前面博主喜欢二次元，想着在读研期间做点对自己有意义的事，因此选择了动漫人物生成方向(呜呜呜，太感谢导师理解和支持了)…...

编程日记 2024/5/10 9:31:05

SpringBoot实现自己的日志服务

日志服务是作为软件开发架构的必备服务之一，一直都是我们所关注，所考虑的服务关键点，一个优秀的日志服务可以为项目的维护提供有力的支持，提高了系统的可靠性。前言如何设计一个优秀而又可靠的日志服务，是一直以来都…...

编程日记 2024/5/9 20:57:12

基于ssm流浪动物救助及领养管理系统（文档）024

大家好✌！我是CZ淡陌。一名专注以理论为基础实战为主的技术博主，将再这里为大家分享优质的实战项目，本人在Java毕业设计领域有多年的经验，陆续会更新更多优质的Java实战项目，希望你能有所收获，少走一些弯路…...

编程日记 2024/5/10 5:30:17

maven安装及配置(IDEA版)简洁

1.下载Maven：您可以从Maven官方网站（https://maven.apache.org/download.cgi）下载适合您操作系统的Maven版本，并解压缩到您想要安装的位置。 2.配置环境变量：将Maven的bin目录添加到PATH环境变量中，这样…...

编程日记 2024/5/10 10:41:25

最全Linux应用开发解析（持续更新）

一、文件IO 1.1 文件描述符在 Linux 操作系统中的一切都被抽象成了文件，那么一个打开的文件是如何与应用程序进行对应呢？ 解决方案是使用文件描述符（file descriptor，简称fd），当在进程中打开一个现有文…...

编程日记 2024/4/24 14:22:17

SpringBoot学习笔记下

文章目录1 接口架构风格 —RESTful1.1 REST1.2 在页面中或者ajax中，支持put，delete请求2 Spring Boot 集成 Redis2.1 redis起步依赖2.2 对比 StringRedisTemplate 和 RedisTemplate3 SpringBoot集成Dubbo3.1 看 SpringBoot继承Dubbo的文档3.2 公共项目7.…...

编程日记 2024/5/4 14:25:01

小米12/12S/13Pro手机MIUI14系统小黄鸟（HttpCanary）CA证书无法注入问题

很多用户获取ROOT是为了抓包，这里一般常常依赖一款名叫HttpCanary的软件，因软件图标是一只小鸟，我们经常叫他小黄鸟。从日常使用上来看，黄鸟确实有抓包获取数据等功能，也在多个手机上实践成功，网上相关教…...

编程日记 2024/4/12 21:11:06

SpringCloud学习笔记（四）Docker

一、Docker如何解决依赖的兼容问题将应用的libs（函数库）、Deps（依赖）、配置与应用一起打包，形成可移植镜像Docker应用运行在容器中，使用沙箱机制，相互隔离二、Dokcer如何解决开发、测试、生…...

编程日记 2024/5/10 15:23:48

SAP 批量修改工艺路线和 BOM

1、在运维的过程中经常会遇到用户需要批量更改组件，或者是批量更改数量，还是组件里面的一些标识，当处理这些批量数据处理的业务时，BOM的批量更改一个想到的就是CS20，但是CS20当BOM需要替换的时候就不是很适用。新增的组…...

编程日记 2024/5/1 7:56:16

基于OpenTelemetry实现可观测性-Part 4 Collector

译注：这是一个系列，共分成6部分，这是第4部分。翻译自：https://trstringer.com/otel-part4-collector/在上一篇博文中，我们讨论了如何使用 SDK 和追踪器提供者从进程获取遥测数据。存在很多不同类型的导出器&#xff0c…...

编程日记 2024/5/9 22:43:08

STM32学习（十二）

软件定时原理使用纯软件（CPU死等）的方式实现定时（延时）功能。不精准：函数调用压栈进栈需要耗费额外的时间；流水线使得程序执行时间不确定。CPU死等。定时器定时原理使用精准的时基，通过…...

编程日记 2024/5/9 23:57:31

Python毕业设计推荐

今天给大家推荐4个基于python的毕业设计/课程设计 1 网上商城系统这是一个基于pythonvue开发的商城网站，平台采用B/S结构，后端采用主流的Python语言进行开发，前端采用主流的Vue.js进行开发。整个平台包括前台和后台两个部分。前台功能…...

编程日记 2024/5/4 0:38:05

组装式交付-云巧知多少

组装式交付-云巧知多少组装式交付背景云巧什么是云巧呢？云巧的优势丰富的组件，提升代码复用全面的集成方式，支持模块化组装云原生标准，预集成阿里云产品云巧的构成云巧组件云巧资产市场云巧生态云巧工坊总结组装式交付背景一直…...

编程日记 2024/5/8 6:26:49

「解析」牛客网-华为机考企业真题 41-60

又是一年春招时，有幸收到华为自动驾驶算法岗，之前刷题不多，在此汇总下牛客网的真题，主要采用Python编写，个人觉得语言只是实现工具而已，并不是很关键，Python简洁易懂，更加适合算法工…...

编程日记 2024/5/9 23:51:19

RPA机器人在信息化管理、报告生成实现自动化成为生态环境局新宠

随着人们对环境和自然资源的保护意识逐渐增强，我国在环保领域的投入力度也越来越大。然而，环境保护任务的繁重与复杂，也意味着环保执法机关需要更加高效、精准的手段来完成任务。这时，“机器人流程自动化”（简称RPA&am…...

编程日记 2024/5/10 20:01:53

关于线程池你了解些什么?

前言学习线程池的思维导图线程池是什么?它有什么用?虽然线程比进程更轻量级,但是每个进程所占的资源空间是有限,如果我们频繁创建和销毁线程也会消耗很多CPU资源,那么我们该如何解决这个问题呢?官方解释:线程池是一种多线程处理形式,其处理过程可以将多个任务添加到阻塞队列…...

编程日记 2024/4/29 10:16:59

基于MATLAB编程的萤火虫改进帝国竞争算法求解多目标优化，FA-ICA目标寻优

目录背影帝国竞争基本定义优点萤火虫原理改进思路基于萤火虫改进帝国竞争多目标求解代码结果分析展望背影多目标多参数优化是常遇到的优化问题，有很多传统算法可以求解，比如fiminmax,fmincon等，但是都容易陷入局部最优，本文用帝国竞争优化萤火虫算法进行多目…...

编程日记 2024/4/16 13:13:22

低代码开发：助力企业高效实现数字转型的一大利器

随着互联网、移动互联网、物联网等技术的迅速普及和应用，数字经济时代的到来，人们的生产、消费和生活方式都发生了巨大的变化，而传统企业也面临着巨大的挑战和机遇。在数字经济时代，数据成为一种重要的生产要素。数据成为一种重要…...

编程日记 2024/5/9 7:47:15

centos7安装mysql并添加密码

网上找的教程有的是不能用，有的是改密码有问题，下面这个教程亲测可用 #安装wget,wget是Linux中的一个下载文件的工具 yum -y install wget #使用wget下载文件 wget http://repo.mysql.com/mysql-community-release-el7-5.noarch.rpm rpm -ivh mysql-com…...

编程日记 2024/5/1 17:58:39

大数据未来发展怎么样？

就目前情况来看，大数据行业前景不错薪资待遇好，也有越来越多的人选择大数据行业，各大名企对于大数据人才需求不断上涨。大数据从业领域很宽广，不管是科技领域还是食品产业，零售业等都是需要大数据人才进行大数据的处…...

编程日记 2024/5/3 0:45:12

图书管理系统（考试样品）

一、执行下面的sql CREATE DATABASE bms CHARACTER SET utf8mb4;USE bms;DROP TABLE IF EXISTS tb_book;CREATE TABLE tb_book (id INT NOT NULL AUTO_INCREMENT,name VARCHAR(20) NOT NULL,desc TEXT ,type_id INT DEFAULT NULL,PRIMARY KEY (id) ) ; INSERT INTO tb_book VA…...

编程日记 2024/5/5 22:26:33

1. 题目介绍（39. 数组中出现次数超过一半的数字）

2. 题解

2.1 暴力穷举 – O(n2)

2.2 数组排序法 – O(nlogn)

2.3 摩尔投票法（原书题解2） – O(n)

3. 参考资料

相关文章：

2.1 暴力穷举 – O(n²)