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,看下使用的多级…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
