【第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- 思路 栈实现四种情况处理 ① 遇到数字,进行倍数相加 、②遇到左括号,压栈之前的元素、③遇到右括号弹出,栈进行…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
