算法通关村-----数组中元素出现次数问题
数组中出现次数超过一半的数字
问题描述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。你可以假设数组是非空的,并且给定的数组总是存在多数元素。详见剑指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)时间复杂度,常数空间复杂度的算法。此时我们可以考虑常数计数或者为运算等常见方式。
相关文章:
算法通关村-----数组中元素出现次数问题
数组中出现次数超过一半的数字 问题描述 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。你可以假设数组是非空的,并且给定的数组总是存在多数元素。详见剑指offer39 问题分析 最直接的方式就是使用hashMap,遍历给定数组,…...
Qt-键盘消息的传递-键盘消息的获取-C++
文章目录 1.概述2.焦点3.强制获取键盘消息4.键盘常用组合方法5.总结 1.概述 QKeyEvent 类用来描述一个键盘事件。当键盘按键被按下或者被释放时,键盘事件便会被发送给拥有键盘输人焦点的部件。 QKeyEvent 的 key() 函数可以获取具体的按键,对于 Qt 中给…...

数据结构与算法(五)--链表概念以及向链表添加元素
一、前言 今天我们学习另一种非常重要的线性数据结构–链表,之前我们已经学习了三种线性数据结构,分别是动态数组,栈和队列。其中队列我们额外学习了队列的另一种实现方式–循环队列。其实我们自己实现过前三个数据结构就知道,它…...

计算机视觉与深度学习-图像分割-视觉识别任务02-目标检测-【北邮鲁鹏】
目录标题 参考目标检测定义深度学习对目标检测的作用单目标检测多任务框架多任务损失预训练模型姿态估计 多目标检测问题滑动窗口(Sliding Window)滑动窗口缺点 AdaBoost(Adaptive Boosting)参考 区域建议 selective search 思想慢…...

Flink——Flink检查点(checkpoint)、保存点(savepoint)的区别与联系
Flink checkpoint Checkpoint是Flink实现容错机制最核心的功能,能够根据配置周期性地基于Stream中各个Operator的状态来生成Snapshot,从而将这些状态数据定期持久化存储下来,从而将这些状态数据定期持久化存储下来,当Flink程序一…...

[篇五章五]-如何禁用 Windows Defender-我的创作纪念日
################################################## 目录 禁用掉烦人的 Windows Defender 在本地组策略编辑器中禁用 Windows Defende 关闭 Microsoft Defender 防病毒 禁止 Defender 开机自动运行 重新激活 Windows Defender #######################################…...

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

【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对象转换方面,springboot默认使用的是MappingJackson2HttpMessageConverter。常规需求,在工程中使用阿里的FastJson作为json对象的转换器。 FastJson SerializerFeatures WriteNullListAsEmpty :List字段如果为null,输出为[],而非nu…...

2023-09-20 Android CheckBox 让文字显示在选择框的左边
一、CheckBox 让文字在选择框的左边 ,在布局文件里面添加下面一行就可以。 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安装东西的时候弹出这个错误: 1、查看安装在本机的网卡 网卡ens33处于disconnected的状态 nmcli d2、输入命令: nmtui3、选择网卡,然后点击edit 4、移动到Automatically connect按空格键选择,然后移动到OK键按空格…...
关于token续签
通常我们会对token设置一个有效期,于是,就有了token续签的问题。由于token并没有续时机制,如果不能及时的替换掉过期的token,可能会拦截用户正常的请求,用户只能重新登录,如果提交的信息量很大,…...

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

Java中synchronized:特性、使用、锁机制与策略简析
目录 synchronized的特性互斥性可见性可重入性 synchronized的使用方法synchronized的锁机制常见锁策略乐观锁与悲观锁重量级锁与轻量级锁公平锁与非公平锁可重入锁与不可重入锁自旋锁读写锁 synchronized的特性 互斥性 synchronized确保同一时间只有一个线程可以进入同步块或…...
记一次clickhouse手动更改分片数异常
背景:clickhouse中之前是1分片1副本,随着数据量增多,想将分片数增多,于是驻场人员手动添加了分片数的节点信息 <clickhouse><!-- 集群配置 --><clickhouse_remote_servers><feihuang_ck_cluster><sha…...

深度学习论文: ISTDU-Net:Infrared Small-Target Detection U-Net及其PyTorch实现
深度学习论文: ISTDU-Net:Infrared Small-Target Detection U-Net及其PyTorch实现 ISTDU-Net: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
前言 安装过程中发现,YOLO V8一直在更新,现在是2023-9-20的版本,已经和1月份刚发布的不一样了。 eg: 目录已经变了,旧版预测:在ultralytics/yolo/v8/下detect 新版: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的…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...

Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...

让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...

技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...

Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...

《信号与系统》第 6 章 信号与系统的时域和频域特性
目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...