Leetcode 寻找重复数

可以使用 位运算 来解决这道题目。使用位运算的一个核心思想是基于数字的二进制表示,统计每一位上 1 的出现次数,并与期望的出现次数做比较。通过这种方法,可以推断出哪个数字重复。
class Solution {
public:int findDuplicate(vector<int>& nums) {int n = nums.size() - 1; //这里注意是nums.size()-1,因为size是n + 1,所以数字取值范围是 [1,n]int countNum = 0; int expectedNum = 0;int result = 0;//遍历32位,题目n<=10^5,所以最大数也足够用32位来表示了for(int bit = 0; bit < 32; ++bit) {//遍历每一位时,首先需要在循环初始将这两个计数器清零。或者在循环末尾处清零。countNum = 0;expectedNum = 0;//设置掩码int mask = 1 << bit; //1左移bit位,每左移1次相当于乘2//然后数组中每个数字和当前mask进行与运算,判断当前位 值为1的数字个数for(int num : nums) {if(num & mask) {countNum++;}}//然后区间[1,n]每个数字与当前mask进行与运算,判断当前位 值为1的数字个数for(int i = 1; i <= n; ++i) {if(i & mask) {expectedNum++;}}//然后如果当前位的countNum > expectedNum, 说明重复数字在当前位的值为1;if(countNum > expectedNum) {result = result | mask;}//countNum = 0;//expectedNum = 0;}return result;}
};
解释:
- 由于
nums数组长度是n + 1,所以它包含从 1 到n的数字,且有一个重复数字。 - 我们逐位检查每一个 bit(从 0 到 31),统计
nums数组中哪些数字在该位上是 1,接着统计从 1 到n的数字在该位上是 1 的个数。 - 如果
nums中在某个位上的 1 的个数多于从 1 到n的数字在该位上的 1 的个数,说明重复的数字在该位上是 1。 - 最终通过将这些结果合并(使用按位或运算),我们就能得到重复的数字。
优点:
- 这种方法的时间复杂度为
O(n * log n),因为我们要遍历每个 bit 位,而每次统计的复杂度为O(n)。 - 空间复杂度为
O(1),因为只使用了常量级的额外空间。
这是一个比较巧妙的位运算解法,适用于这类寻找重复数的场景。
相关文章:
Leetcode 寻找重复数
可以使用 位运算 来解决这道题目。使用位运算的一个核心思想是基于数字的二进制表示,统计每一位上 1 的出现次数,并与期望的出现次数做比较。通过这种方法,可以推断出哪个数字重复。 class Solution { public:int findDuplicate(vector<i…...
大一新生以此篇开启你的算法之路
各位大一计算机萌新们,你们好,本篇博客会带领大家进行算法入门,给各位大一萌新答疑解惑。博客文章略长,可根据自己的需要观看,在博客中会有给大一萌新问题的解答,请不要错过。 入门简介: 算法…...
【AI大模型】ChatGPT模型原理介绍(上)
目录 🍔 什么是ChatGPT? 🍔 GPT-1介绍 2.1 GPT-1模型架构 2.2 GPT-1训练过程 2.2.1 无监督的预训练语言模型 2.2.2 有监督的下游任务fine-tunning 2.2.3 整体训练过程架构图 2.3 GPT-1数据集 2.4 GPT-1模型的特点 2.5 GPT-1模型总结…...
基于UE5和ROS2的激光雷达+深度RGBD相机小车的仿真指南(五):Blender锥桶建模
前言 本系列教程旨在使用UE5配置一个具备激光雷达深度摄像机的仿真小车,并使用通过跨平台的方式进行ROS2和UE5仿真的通讯,达到小车自主导航的目的。本教程默认有ROS2导航及其gazebo仿真相关方面基础,Nav2相关的学习教程可以参考本人的其他博…...
C++竞赛初阶L1-15-第六单元-多维数组(34~35课)557: T456507 图像旋转
题目内容 输入一个 n 行 m 列的黑白图像,将它顺时针旋转 90 度后输出。 输入格式 第一行包含两个整数 n 和 m,表示图像包含像素点的行数和列数。1≤n≤100,1≤m≤100。 接下来 n 行,每行 m 个整数,表示图像的每个像…...
无线领夹麦克风哪个牌子好?西圣、罗德、猛犸领夹麦克风深度评测
如今短视频和直播行业蓬勃发展,无线领夹麦克风成为了许多创作者不可或缺的工具。然而,市场上的无线领夹麦克风品牌众多、质量参差不齐,为了帮助大家挑选到满意的产品,我作为数码测评博主,对无线领夹麦克风市场进行了…...
React Native 0.76,New Architecture 将成为默认模式,全新的 RN 来了
关于 React Native 的 New Architecture 概念,最早应该是从 2018 年 RN 团队决定重写大量底层实现开始,因为那时候 React Native 面临各种结构问题和性能瓶颈,最终迫使 RN 团队开始进行重构。 而从 React Native 0.68 开始,New A…...
Java并发:互斥锁,读写锁,Condition,StampedLock
3,Lock与Condition 3.1,互斥锁 3.1.1,可重入锁 锁的可重入性(Reentrant Locking)是指在同一个线程中,已经获取锁的线程可以再次获取该锁而不会导致死锁。这种特性允许线程在持有锁的情况下,可…...
客户端负载均衡Ribbon实例
文章目录 一,概述二,实现过程三,项目源码1. 源码放送:2. 部署方式 四,功能演示五,其他 一,概述 一般来说,提到负载均衡,大家一般很容易想到浏览器 -> NGINX -> 反…...
MySQL数据库负载均衡
数据库负载均衡是通过将数据库请求分散到多个数据库服务器上,以提高数据库的处理能力和可用性。在高并发的场景下,使用数据库负载均衡器可以有效避免单点故障,提高系统的整体性能和可靠性。 数据库负载均衡器 数据库负载均衡器可以是硬件设…...
达梦CASE_SENSITIVE参数解析
1. 参数含义 标识符大小写敏感,默认值为 Y。 当大小写敏感时,小写的标识符应用双引号括起,否则被转换为大写;当大小写不敏感时,系统不自动转换标识符的大小写,在标识符比较时也不区分大小写。 CASE_SENS…...
酒店智能轻触开关工作原理
在现代化酒店中,智能轻触开关已成为提升宾客居住体验的重要设备之一。这些开关不仅操作便捷,而且功能丰富,能够实现对灯光、窗帘、空调等设备的精准控制。本文将深入探讨酒店智能轻触开关的工作原理。 一、智能轻触开关的基本概念 智能轻触开…...
web基础之RCE
简介:RCE称为远程代码执行漏洞;是互联网的一种安全漏洞;攻击者可以直接向后台服务器远程注入操作系统命令;从而操控后台系统;也是CTF比较常考的一个方面 1、eval执行 (1)分析后端代码…...
c语言--水仙花数,求Sn的前五项和
用C语言实现输出水仙花数 什么是“水仙花数”? 所谓“水仙花数”是指一个n位数,其各位数字n次方之和等于该数本身。 例如:1531 ^3 5 ^3 3 ^3 如何求解水仙花数? 思路: 步骤1:先计算出数i的位数&#x…...
SpringBoot教程(二十八) | SpringBoot集成Elasticsearch(Java High Level Rest Client方式)
SpringBoot教程(二十八) | SpringBoot集成Elasticsearch(Java High Level Rest Client方式) 前言添加maven依赖yml配置ElasticsearchConfig 连接配置类EsUtil 工具类开始测试 前言 由ES官方提供,代码语法和DSL语法相似…...
【Vue3】常用的响应式数据类型
ref 定义基本类型 <template><div>{{ sum }}</div> </template><script setup> import { ref } from vuelet sum ref(10)const btn () > {sum.value 200 } </srcipt>reactive 定义复杂类型 <template><div>{{ sum }…...
搭建本地DVWA靶场教程 及 靶场使用示例
1. DVWA简介 DVWA(Damn Vulnerable Web Application)一个用来进行安全脆弱性鉴定的PHP/MySQL Web 应用平台,旨在为网络安全专业人员测试自己的专业技能和工具提供合法的环境,帮助web开发者更好的理解web应用安全防范的过程。 DVW…...
60. n 个骰子的点数【难】
comments: true difficulty: 简单 edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9860.%20n%E4%B8%AA%E9%AA%B0%E5%AD%90%E7%9A%84%E7%82%B9%E6%95%B0/README.md 面试题 60. n 个骰子的点数 题目描述 把n个骰子扔在地上,所…...
高性能编程:无锁队列
目录 1. 无锁队列 1.1 无锁 1.1.1 阻塞(Blocking) 1.1.2 无锁(Lock-Free) 1.1.3 无等待(Wait-Free) 1.2 队列 1.2.1 链表实现的队列 1.2.2 数组实现的队列 1.2.3 混合实现的队列 1.3 多线程中的先…...
word标题排序编号错误
1.问题:word中有时会出现当前编号是2.1、3.1、4.1,下级编号却从1.1.1开始的情况,类似情况如下: 2.原因:此问题多为编号4.1、4.2和编号4.1.1使用的多级编号模板不一样,可以选中4.2,看下使用的多级…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
