【第0006页 · 数组】寻找重复数
【前言】本文以及之后的一些题解都会陆续整理到目录中,若想了解全部题解整理,请看这里:

第0006页 · 寻找重复数
今天想讨论的一道题在 LeetCode 上评论也是颇为“不错”。有一说一,是道好题,不过我们还是得先理解了它才算真正的好题。这里我们展示一种使用二进制的做法,希望能帮到你哟!
【寻找重复数】给定一个包含
n + 1个整数的数组nums,其数字都在[1, n]范围内(包括1和n),可知至少存在一个重复的整数。现在假设nums只有一个重复的整数,请返回这个重复的数。要求:你设计的解决方案必须不修改数组nums且只用常量级O(1)的额外空间。
示例1 示例2 示例3 输入:nums = [1, 3, 4, 2, 2] 输入:nums = [3, 1, 3, 4, 2] 输入:nums = [3, 3, 3, 3, 3] 输出:2 输出:3 输出:3
【解题分析】这道题目最难的地方莫过于它的要求:只能使用常量级的额外空间!既然不能用一般的方法,我们便另辟蹊径,对所有数 [1, n] 进行二进制展开,举个例子如下表所示:
1 3 4 2 2 x y 第 0 位 1 1 0
0 0 2 2 第 1 位 0 1 0 1 1 3 2 第 2 位 0 0 1 0 0 1 1 对于第 i 位,我们用 x 记录 nums 中所有数满足二进制形式下第 i 位是 1 的数量有多少。用 y 记录 1 ~ n 中所有数在二进制形式下第 i 位是 1 的数量应该有多少。
比如说,上表中第 0 位,nums 中的数有 2 个的二进制形式该位为 1,而 1 ~ 4 中该位为 1 的数有 2 个。
那么怎么找出重复的数呢?假设重复的数是 k,那么,对于 k 二进制展开后所有为 1 的数位必定会导致 x > y。
但是这个结论我们还是需要证明一下的。
【证明】
如果 nums 数组中 target 出现了 2 次,其余的数各出现了 1 次,那么如果 target 的第 i 位为 1,那么 nums 数组的第 i 位 1 的个数 x 恰好比 y 大了 1。如果 target 的第 i 位为 0,那么 x = y。
如果 nums 数组中 target 出现了 3 次及以上,那么必然有一些数不在 nums 数组中。这个时候就相当于我们用 target 替换了这些数,我们要考虑的就是这样的替换对 x 会产生什么影响:
1、如果被替换的数第 i 位为 1,且 target 第 i 位为 1:x 不变,满足 x>y。
2、如果被替换的数第 i 位为 0,且 target 第 i 位为 1:x 加一,满足 x>y。
3、如果被替换的数第 i 位为 1,且 target 第 i 位为 0:x 减一,满足 x≤y。
4、如果被替换的数第 i 位为 0,且 target 第 i 位为 0:x 不变,满足 x≤y。总而言之,在替换后,如果 target 的第 i 位为 1,那么始终满足 x > y;如果为 0,那么每次替换后始终满足 x ≤ y。因此,接下来我们只需要按照位次复原这个数就可以了。
【源码展示】
class Solution { public:int findDuplicate(vector<int>& nums) {int n = nums.size(), ans = 0;// 确定二进制下最高位是多少int bit_max = 31;while (!((n - 1) >> bit_max)) {bit_max -= 1;}for (int bit = 0; bit <= bit_max; bit++) {int x = 0, y = 0;for (int i = 0; i < n; ++i) {if (nums[i] & (1 << bit)) {x += 1;}if (i >= 1 && (i & (1 << bit))) {y += 1;}}if (x > y) {ans |= 1 << bit;}}return ans;} };
相关文章:
【第0006页 · 数组】寻找重复数
【前言】本文以及之后的一些题解都会陆续整理到目录中,若想了解全部题解整理,请看这里: 第0006页 寻找重复数 今天想讨论的一道题在 LeetCode 上评论也是颇为“不错”。有一说一,是道好题,不过我们还是得先理解了它才…...
移情别恋c++ ദ്ദി˶ー̀֊ー́ ) ——10.继承
1.继承的概念及定义 1.1继承的概念 继承(inheritance)机制是面向对象程序设计使代码可以复用的最重要的手段,它允许程序员在保 持原有类特性的基础上进行扩展,增加功能,这样产生新的类,称派生类。继承呈现了面向对象 程序设计的层…...
uniapp+vue3实现双通道透明MP4播放支持小程序和h5
双通道透明MP4视频播放的截图 以下是合成后结果,二个合并在一起进行播放 下载资源,打开运行直接使用看到效果 https://download.csdn.net/download/qq_40039641/89715780...
汇编:嵌入式软件架构学习资源
成为嵌入式软件架构设计师需要掌握多方面的知识,包括嵌入式系统、实时操作系统、硬件接口、软件设计模式等。 以下是一些推荐的博客和网站,可以帮助你深入学习嵌入式软件架构设计: ### 1. **Embedded.com** - **网址**: [Embedded.com](htt…...
python编程知识(实现数据加密和解密)
👨💻个人主页:开发者-曼亿点 👨💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨💻 本文由 曼亿点 原创 👨💻 收录于专栏:…...
如何使div居中?CSS居中终极指南
前言 长期以来,如何在父元素中居中对齐一个元素,一直是一个让人头疼的问题,随着 CSS 的发展,越来越多的工具可以用来解决这个难题,五花八门的招式一大堆,这篇博客,旨在帮助你理解不同的居中方法…...
Redis 篇-深入了解分布式锁 Redisson 原理(可重入原理、可重试原理、主从一致性原理、解决超时锁失效)
🔥博客主页: 【小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍ 本章目录 1.0 基于 Redis 实现的分布式锁存在的问题 2.0 Redisson 功能概述 3.0 Redisson 具体使用 4.0 Redisson 可重入锁原理 5.0 Redisson 锁重试原理 6.0 Redisson WatchDo…...
PostgreSQL中的多版本并发控制(MVCC)深入解析
引言 PostgreSQL作为一款强大的开源关系数据库管理系统,以其高性能、高可靠性和丰富的功能特性而广受欢迎。在并发控制方面,PostgreSQL采用了多版本并发控制(MVCC)机制,该机制为数据库提供了高效的数据访问和更新能力…...
SpringBoot项目-实现简单的CRUD功能和分页查询
背景 本博文主要是创建了一个新的SpringBoot项目,实现基本的增删改查,分页查询,带条件的分页查询功能。是方便初学者学习后端项目的一个比较清晰明了的实践代码,读者可根据博文,从自己动手创建一个新的SpringBoot项目…...
CCF编程能力等级认证GESP—C++2级—20240907
CCF编程能力等级认证GESP—C2级—20240907 单选题(每题 2 分,共 30 分)判断题(每题 2 分,共 20 分)编程题 (每题 25 分,共 50 分)数位之和小杨的矩阵 单选题(每题 2 分,共…...
C语言手撕实战代码_二叉排序树(二叉搜索树)_构建_删除_插入操作详解
二叉排序树习题1.设计算法构建一棵二叉排序树(又称二叉搜索树BST)2.查找二叉排序树中结点为x的结点所在的层数3.删除二叉排序树T中值为x的结点4.查找二叉排序树中所有小于key的关键字5.编写算法,将一棵二叉树t分解成两棵二叉排序树t1和t2,使得t1中的所有…...
YC教父的创始人模式VS职业经理人模式:AI时代的独立开发者崛起
近年来,由风投资助的创始人模式因其相对较低的入门门槛而在创业圈内广受欢迎。然而,真正的挑战在于独立开发者(一人商业)模式。随着AI技术的飞速发展,一人商业模式有望成为未来的主流。本文将探讨独立开发者的工作范围…...
[SUCTF 2019]Pythonginx
给了源码 app.route(/getUrl, methods[GET, POST]) def getUrl():url request.args.get("url")host parse.urlparse(url).hostnameif host suctf.cc:return "我扌 your problem? 111"parts list(urlsplit(url))host parts[1]if host suctf.cc:retu…...
省市县相关校验sql随笔
1.层级校验 要判断一个给定的省、市、区(县)名字是否符合正确的层级关系,假设你的表结构如下: CREATE TABLE regions (id INT PRIMARY KEY,name VARCHAR(255),parent_id INT, -- 指向上一级区域的id,例如市的parent_id指向省的…...
uniapp ios sticky定位,内部 u-tabs(包含scroll-view)消失问题
uniapp中用sticky定位时,元素内部如果有scroll-view,ios在触发bounce机制时,scroll-view的元素会消失,解决方法是页面上包一层高度为100vh的scroll-view <scroll-view style"height: 100vh;" scroll-y scrolltolowe…...
web群集--nginx配置文件location匹配符的优先级顺序详解及验证
文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配(Exact Match)2. 正则表达式匹配(Regex Match)3. 前缀匹配(Prefix Match) 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中࿰…...
Vivado编译报错黑盒子问题
1 问题描述 “Black Box Instances: Cell **** of type ** has undefined contents and is considered a back box. The contents of this cell must be defined for opt_design to complete successfully.” 检查工程代码提示的模块,该模块为纯手写的Veril…...
【建造者模式】
建造者模式 Builder Pattern 属于创建型模式是将一个复杂对象的构建与它的标识分离,使得同样的构建过程可以创建不同的表示关键点:用户只需要指定需要建造的类型就可以获得对象,建造过程及细节不需要了解 实现 demo 需要构建的对象 Data pu…...
自动化表格处理的革命:智能文档系统技术解析
在当今数据驱动的商业环境中,表格数据的自动化处理成为了企业提高效率、降低成本的关键。企业智能文档系统在智能表格识别方面展现出卓越的性能,通过精准识别和处理各种通用表格,显著提升了企业文档管理的智能化水平。本文将深入探讨该系统在…...
【Hot100】LeetCode—394. 字符串解码
目录 1- 思路栈实现四种情况处理 2- 实现⭐394. 字符串解码——题解思路 3- ACM 实现 原题链接:394. 字符串解码 1- 思路 栈实现四种情况处理 ① 遇到数字,进行倍数相加 、②遇到左括号,压栈之前的元素、③遇到右括号弹出,栈进行…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
