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

算法通关村-----数组中元素出现次数问题

数组中出现次数超过一半的数字

问题描述

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。你可以假设数组是非空的,并且给定的数组总是存在多数元素。详见剑指offer39

问题分析

最直接的方式就是使用hashMap,遍历给定数组,将数字和对应出现次数存储在hashMap中,然后再遍历hashMap,找到出现次数最大的数字。除此之外,我们还可以将数据进行排序,升序和降序均可,排序后,出现次数超过一半的元素一定出现在数组的中位数位置。除此之外,还有一种巧妙解法,设立两个变量,num和count,num用于存储当前遍历到的元素,count用于存储次数,如果count为0,则当前元素不可能是出现次数超过一半的元素,则遍历下一个元素。

代码实现

使用HashMap解法

public int majorityElement(int[] nums) {Map<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);}else{map.put(nums[i],1);}}int maxCount = Integer.MIN_VALUE;int maxNum = Integer.MIN_VALUE;for(int num:map.keySet()){if(map.get(num)>maxCount){maxCount = map.get(num);maxNum = num;}}return maxNum;
}

使用排序解法

public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length/2];
}

巧妙解法

public int majorityElement(int[] nums) {int result=0;int count=0;for(int num:nums){if(count==0){result = num;}count += result==num?1:-1;}return result;
}

数组中只出现一次的数字

问题描述

给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。详见leetcode136

问题分析

使用HashMap存储数组元素和元素出现的次数,遍历HashMap,找到出现一次的元素,或者利用HashSet存储元素,利用集合的不可重复性,如果可以添加到集合中,说明当前遍历到的元素在数组中出现一次,直接添加,如果不能添加,说明当前遍历到的元素在数组中出现两次,移除HashSet中的当前元素,最后返回HashSet中的元素,即为数组中只出现一次的元素。除此之外,我们还可以利用位运算来实现。遍历数组元素,进行异或运算,出现两次的元素异或运算结果为0,所有元素的异或运算结果为数组中只出现一次的元素

代码实现

使用HashSet

public int singleNumber(int[] nums) {Set<Integer> set = new HashSet<>();for(int num: nums){if(!set.add(num)){set.remove(num);}}Integer[] array = set.toArray(new Integer[set.size()]);return array[0];
}

使用异或运算

public int singleNumber(int[] nums) {int res = 0;for(int num:nums){res^=num;}return res;
}

137. 只出现一次的数字 II

问题描述

给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

问题分析

使用HashMap存储数组元素和元素出现的次数,遍历HashMap,找到出现一次的元素。另外我们也可以使用位运算来实现对于出现3次的元素,每一位为0或者1,相加为0或者3,可以将每一位相加后对3取余,即为只出现一次的元素的对应位的值。

代码实现

使用位运算实现

public int singleNumber(int[] nums) {int res = 0;for(int i=0;i<32;i++){int total = 0;for(int num:nums){total+=((num>>i)&1);}if(total%3!=0){res |= (1<<i);}}return res;
}

总结

元素出现次数问题通用方法就是使用HashMap存储元素和对应次数,或许遍历map即可得到想要出现次数的元素。这种方法需要遍历一次数组,遍历一次map,使用一个map,时间复杂度为O(n),空间复杂度为O(n),面试时,可能不允许使用Hash或者集合,即需要我们设计O(n)时间复杂度,常数空间复杂度的算法。此时我们可以考虑常数计数或者为运算等常见方式。

相关文章:

算法通关村-----数组中元素出现次数问题

数组中出现次数超过一半的数字 问题描述 数组中有一个数字出现的次数超过数组长度的一半&#xff0c;请找出这个数字。你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。详见剑指offer39 问题分析 最直接的方式就是使用hashMap,遍历给定数组&#xff0c…...

Qt-键盘消息的传递-键盘消息的获取-C++

文章目录 1.概述2.焦点3.强制获取键盘消息4.键盘常用组合方法5.总结 1.概述 QKeyEvent 类用来描述一个键盘事件。当键盘按键被按下或者被释放时&#xff0c;键盘事件便会被发送给拥有键盘输人焦点的部件。 QKeyEvent 的 key() 函数可以获取具体的按键&#xff0c;对于 Qt 中给…...

数据结构与算法(五)--链表概念以及向链表添加元素

一、前言 今天我们学习另一种非常重要的线性数据结构–链表&#xff0c;之前我们已经学习了三种线性数据结构&#xff0c;分别是动态数组&#xff0c;栈和队列。其中队列我们额外学习了队列的另一种实现方式–循环队列。其实我们自己实现过前三个数据结构就知道&#xff0c;它…...

计算机视觉与深度学习-图像分割-视觉识别任务02-目标检测-【北邮鲁鹏】

目录标题 参考目标检测定义深度学习对目标检测的作用单目标检测多任务框架多任务损失预训练模型姿态估计 多目标检测问题滑动窗口&#xff08;Sliding Window&#xff09;滑动窗口缺点 AdaBoost&#xff08;Adaptive Boosting&#xff09;参考 区域建议 selective search 思想慢…...

Flink——Flink检查点(checkpoint)、保存点(savepoint)的区别与联系

Flink checkpoint Checkpoint是Flink实现容错机制最核心的功能&#xff0c;能够根据配置周期性地基于Stream中各个Operator的状态来生成Snapshot&#xff0c;从而将这些状态数据定期持久化存储下来&#xff0c;从而将这些状态数据定期持久化存储下来&#xff0c;当Flink程序一…...

[篇五章五]-如何禁用 Windows Defender-我的创作纪念日

################################################## 目录 禁用掉烦人的 Windows Defender 在本地组策略编辑器中禁用 Windows Defende 关闭 Microsoft Defender 防病毒 禁止 Defender 开机自动运行 重新激活 Windows Defender #######################################…...

什么情况下使用微服务?

单体架构图参考网络&#xff1a; 1. 什么是单体应用 单体应用就是将应用程序的所有功能都打包成一个独立的单元&#xff0c;最终以一个WAR包或JAR包存在&#xff0c;没有外部的任何依赖&#xff0c;里面包含DAO、Service、UI等所有的逻辑。 优点&#xff1a; &#xff11;&…...

【Linux】Ubuntu美化主题【教程】

【Linux】Ubuntu美化主题【教程】 文章目录 【Linux】Ubuntu美化主题【教程】1. 安装优化工具Tweak2.下载自己喜欢的主题3. 下载自己喜欢的iconReference 1. 安装优化工具Tweak 首先安装优化工具Tweak sudo apt-get install gnome-tweak-tool安装完毕后在菜单中打开Tweak 然后…...

spring-boot2.x,使用EnableWebMvc注解导致的自定义HttpMessageConverters不可用

在json对象转换方面&#xff0c;springboot默认使用的是MappingJackson2HttpMessageConverter。常规需求&#xff0c;在工程中使用阿里的FastJson作为json对象的转换器。 FastJson SerializerFeatures WriteNullListAsEmpty &#xff1a;List字段如果为null,输出为[],而非nu…...

2023-09-20 Android CheckBox 让文字显示在选择框的左边

一、CheckBox 让文字在选择框的左边 &#xff0c;在布局文件里面添加下面一行就可以。 android:layoutDirection"rtl" 即可实现 android:paddingStart"10dp" 设置框文间的间距 二、使用的是left to right <attr name"layoutDirection">&…...

目标检测YOLO实战应用案例100讲-基于改进YOLOv5的口罩人脸检测

目录 前言 国内外研究现状 目标检测研究发展 国内外口罩人脸检测研究现状...

CentOS7 yum安装报错:“Could not resolve host: mirrorlist.centos.org; Unknown error“

虚拟机通过yum安装东西的时候弹出这个错误&#xff1a; 1、查看安装在本机的网卡 网卡ens33处于disconnected的状态 nmcli d2、输入命令&#xff1a; nmtui3、选择网卡&#xff0c;然后点击edit 4、移动到Automatically connect按空格键选择&#xff0c;然后移动到OK键按空格…...

关于token续签

通常我们会对token设置一个有效期&#xff0c;于是&#xff0c;就有了token续签的问题。由于token并没有续时机制&#xff0c;如果不能及时的替换掉过期的token&#xff0c;可能会拦截用户正常的请求&#xff0c;用户只能重新登录&#xff0c;如果提交的信息量很大&#xff0c;…...

淘宝分布式文件存储系统( 二 ) -TFS

淘宝分布式文件存储系统( 二 ) ->>TFS 目录 : 大文件存储结构哈希链表的结构文件映射原理及对应的API文件映射头文件的定义 大文件存储结构 : 采用块(block)文件的形式对数据进行存储 , 分成索引块,主块 , 扩展块 。所有的小文件都是存放到主块中的 &#xff0c;扩展块…...

Java中synchronized:特性、使用、锁机制与策略简析

目录 synchronized的特性互斥性可见性可重入性 synchronized的使用方法synchronized的锁机制常见锁策略乐观锁与悲观锁重量级锁与轻量级锁公平锁与非公平锁可重入锁与不可重入锁自旋锁读写锁 synchronized的特性 互斥性 synchronized确保同一时间只有一个线程可以进入同步块或…...

记一次clickhouse手动更改分片数异常

背景&#xff1a;clickhouse中之前是1分片1副本&#xff0c;随着数据量增多&#xff0c;想将分片数增多&#xff0c;于是驻场人员手动添加了分片数的节点信息 <clickhouse><!-- 集群配置 --><clickhouse_remote_servers><feihuang_ck_cluster><sha…...

深度学习论文: ISTDU-Net:Infrared Small-Target Detection U-Net及其PyTorch实现

深度学习论文: ISTDU-Net&#xff1a;Infrared Small-Target Detection U-Net及其PyTorch实现 ISTDU-Net&#xff1a;Infrared Small-Target Detection U-Net PDF: https://doi.org/10.1109/LGRS.2022.3141584 PyTorch代码: https://github.com/shanglianlm0525/CvPytorch PyTo…...

图像识别-YOLO V8安装部署-window-CPU-Pycharm

前言 安装过程中发现&#xff0c;YOLO V8一直在更新&#xff0c;现在是2023-9-20的版本&#xff0c;已经和1月份刚发布的不一样了。 eg: 目录已经变了&#xff0c;旧版预测:在ultralytics/yolo/v8/下detect 新版&#xff1a;ultralytics/models/yolo/detect/predict.py 1.安…...

js禁用F1至F12、禁止缩放、取消选中并且取消右键操作、打印、拖拽、鼠标点击弹出自定义信息、禁用开发者工具js

禁用js //禁止缩放 //luwenjie hualun window.addEventListener(mousewheel, function (event) {if (event.ctrlKey true || event.metaKey) {event.preventDefault();} }, {passive: false});//firefox window.addEventListener(DOMMouseScroll, function (event) {if (even…...

Zabbix5.0_介绍_组成架构_以及和prometheus的对比_大数据环境下的监控_网络_软件_设备监控_Zabbix工作笔记

z 这里Zabbix可以实现采集 存储 展示 报警 但是 zabbix自带的,展示 和报警 没那么好看,我们可以用 grafana进行展示,然后我们用一个叫睿象云的来做告警展示, 会更丰富一点. 可以看到 看一下zabbix的介绍. 对zabbix的介绍,这个zabbix比较适合对服务器进行监控 这个是zabbix的…...

百度SEO优化TDK介绍(分析下降原因并总结百度优化SEO策略)

TDK是SEO优化中很重要的部分&#xff0c;包括标题&#xff08;Title&#xff09;、描述&#xff08;Description&#xff09;和关键词&#xff08;Keyword&#xff09;&#xff0c;为百度提供网页内容信息。其中标题是最重要的&#xff0c;应尽量突出关键词&#xff0c;同时描述…...

搭建自动化 Web 页面性能检测系统 —— 设计篇

页面性能对于用户体验、用户留存有着重要影响&#xff0c;当页面加载时间过长时&#xff0c;往往会伴随着一部分用户的流失&#xff0c;也会带来一些用户差评。性能的优劣往往是同类产品中胜出的影响因素&#xff0c;也是一个网站口碑的重要评判标准。 一、名称解释 前端监控…...

记一次 mysql 数据库定时备份

环境&#xff1a;Centos 7.9 数据库&#xff1a;mysql 8.0.30 需求&#xff1a;生产环境 mysql 数据&#xff08;约670MB&#xff09;备份。其中存在大字段、longblob字段 参考博客&#xff1a;Linux环境下使用crontab实现mysql定时备份 - 知乎 一、数据库备份 1. 备份脚本。创…...

淘宝分布式文件存储系统(一) -TFS

淘宝分布式文件存储系统( 一 ) ->>TFS 目录 : 什么是文件系统文件存储的一些概念文件的结构系统读取文件的方式为什么采用大文件结构的原因 文件系统 : 将我们的数据整合成目录或者文件,提供对文件的存取接口,基于文件的权限进行访问,简单的说,文件系统就是对文件进行…...

LLM各层参数详细分析(以LLaMA为例)

网上大多分析LLM参数的文章都比较粗粒度&#xff0c;对于LLM的精确部署不太友好&#xff0c;在这里记录一下分析LLM参数的过程。 首先看QKV。先上transformer原文 也就是说&#xff0c;当h&#xff08;heads&#xff09; 1时&#xff0c;在默认情况下&#xff0c; W i Q W_i…...

linux ansible(三)

ansible 配置详解 3.1 ansible 安装方式 ansible安装常用两种方式&#xff0c;yum安装和pip程序安装 3.1.1 使用 pip&#xff08;python的包管理模块&#xff09;安装 需要安装一个python-pip包&#xff0c;安装完成以后&#xff0c;则直接使用pip命令来安装我们的ansible包 …...

Anaconda和Pycharm详细安装 配置教程

Anaconda&#xff1a;是一个开源的Python发行版本&#xff0c;其中包含了conda、Python等180多个科学包及其依赖项。【Anaconda下载】 PyCharm&#xff1a;PyCharm是一种Python IDE&#xff0c;带有一整套可以帮助用户在使用Python语言开发时提高其效率的工具。【PyCharm下载】…...

利用Linux虚拟化技术实现资源隔离和管理

在现代计算机系统中&#xff0c;资源隔离和管理是非常重要的&#xff0c;特别是在多租户环境下。通过利用Linux虚拟化技术&#xff0c;我们可以实现对计算资源&#xff08;如CPU、内存和存储&#xff09;的隔离和管理&#xff0c;以提供安全、高效、稳定的计算环境。下面将详细…...

12基于MATLAB的短时傅里叶变换( STFT),连续小波变换( CWT),程序已调通,可以直接运行。

基于MATLAB的短时傅里叶变换( STFT),连续小波变换( CWT),程序已调通&#xff0c;可以直接运行...

k8s使用时无法ping通服务器From IP地址 icmp_seq=1 Destination Host Unreachable

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…...

做网站书/seo是什么意思广东话

之前看到园子里的朋友&#xff0c;写了一个自动生成属性的小工具&#xff0c;可惜操作起来不太方便&#xff0c;要切换窗体。而Visual Studio中自带的自动生成属性的功能不好用&#xff0c;每次只能成生成一个&#xff0c;不能批量。今天在整理以前文档的时候&#xff0c;无意中…...

wordpress 4.7.3 id/专业做灰色关键词排名

盒马app刚出现&#xff0c;就吸足了眼球。最近看了看盒马界面&#xff0c;很Q&#xff0c;就想着仿照app写个小程序。 功能介绍 好奇微信小程序是如何制作的&#xff0c;也对盒马app感兴趣&#xff0c;就尝试写了这个盒马小程序。实现了app的部分功能&#xff0c;还有部分功能未…...

怎么样下载app软件/移动网站推广如何优化

https://www.imgtec.com/blog/a-look-at-the-powervr-graphics-architecture-tile-based-rendering/ 一种硬件结构 color target 分成tile 减小带宽 提前&#xff08;fs&#xff09;用depth做隐藏面消除 earlyz一个意思 减小cache missing 一行短了。。 所以early失效的都不可以…...

网站留言效果怎么做/好看的友情链接代码

1、筛选符合条件的记录要筛选顾客为“天津大宇”的所有记录(点击图片动起来)2、筛选符合条件的部分记录要筛选顾客为“天津大宇”的部分记录&#xff0c;可以将“复制到”区域中提前写上需要得到的字段标题。3、筛选同时符合两个条件的记录要筛选同时符合两个条件的记录&#x…...

企业营销网站建设费用预算/北京百度seo

欢迎访问 Snippet:2021/6/24 8:36 下午 致谢: &#x1f330; 手把手带你爬取小姐姐私房照&#x1f34e; 一座城市一个故事 问题概述: &#x1f433; &#x1f42d; 使用Python获取朴缜《东方幻月录》中古风城市图片 &#x1f433; &#x1f42d;方案细节 &#x1f433; 介绍…...

谷歌seo详细教学/福州seo排名公司

Properties类 Properties类介绍特点&#xff1a; 1、Hashtable的子类&#xff0c;map集合中的方法都可以用。 2、该集合没有泛型。键值都是字符串。 3、它是一个可以持久化的属性集。键值可以存储到集合中&#xff0c;也可以存储到持久化的设备(硬盘、U盘、光盘)上。键值的来源…...