【leetcode】寻找重复数
题目链接:寻找重复数
https://leetcode.cn/problems/find-the-duplicate-number/
方法一:快慢指针
因为只有一个数字是重复的,且一个数字正好对应一个唯一的下标,所以可以将数组抽象为一个链表,假定数组为{1,2,3,4,5,6,3} --> {1,2,3,4,5,6},{3,4,5,6},{3,4,5,6}...

slow一次走一步,fast一次走两步,那么当slow与fast相遇的时候,必定是在环内的某一个位置,假设slow走了n步,fast就走了2n步。假设数组首部到环入口的距离为m,那么slow在环内走了n-m的长度, fast走了2n-m个长度,
则有 2n-m = k(n-m) (k != 0)
不妨设 n - m = c 则可知 n%c == 0
现在slow走了n-m步,让slow再走m步就会到达环的入口(n%c == 0),而m正是起点到环入口的距离。
代码
class Solution {
public:int findDuplicate(vector<int>& nums) {//快慢指针//当出现相同的数字时,会形成类似于链表中的环。int fast = 0,slow = 0;while(true){fast = nums[nums[fast]];//fast一次走两步slow = nums[slow];//slow一次走一步if(fast == slow)//两个节点下相遇,必定是在环内部。break;}//当finder == slow时就是环的入口//为什么finder和slow相遇的时候,就是入口?/*假定slow 和 fast 相遇时,fast走了2n步,slow走了n步 环长度为c 起点至环入口就是m则有n%c == 0 n - m 为slow走的距离,当slow再走一个m时,就到环的入口,而m正是起点到环入口的距离*/int finder = 0;while(true){finder = nums[finder];slow = nums[slow];if(slow == finder) break;}return slow;}
};
方法二:二分查找
假定数组q[] = {1,2,3,4,4} q.size() = 5 区间[1,4]
小于等于 1 的数字个数为 1 (1)
小于等于 2 的数字个数为 2 (1、2)
小于等于 3 的数字个数为 4 (1、2 、3)
小于等于 4 的数字个数为 4 (1、2、3、4、4)
可以看到左边的数集合严格小于自身,右边的数集合严格大于自身。当集合中的个数cnt > 指定的数字时,就会出现重复数字。
二分的思想时,当出现一个条件可以使得左半边的数字严格与右半边的数字出现分割就行。
class Solution {
public:int findDuplicate(vector<int>& nums) {int l = 0,r = nums.size()-1;while(l < r){int mid = l + r >> 1;int cnt = 0;for(int i = 0;i < nums.size();i++){if(nums[i] <= mid){cnt++;}}//当出现从cnt > mid 就说明mid的左半部分出现了重复的数字,使得计数大于mid//重复的数字在[l,mid]if(cnt > mid) r = mid;else l = mid + 1;}return l;}
};
相关文章:
【leetcode】寻找重复数
题目链接:寻找重复数https://leetcode.cn/problems/find-the-duplicate-number/ 方法一:快慢指针 因为只有一个数字是重复的,且一个数字正好对应一个唯一的下标,所以可以将数组抽象为一个链表,假定数组为{1,2,3,4,5,…...
LeetCode 1247. Minimum Swaps to Make Strings Equal【数学,贪心,字符串】
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章…...
pid控制加热算法,附代码仓库
1、该项目层次化结构清晰,代码框架耦合度低,可复用性、可移植性强。 2、功能代码与底层硬件无直接关联,无需更改上层应用逻辑,只需更改接口文件,即可移植到不同的硬件平台; 3、使用lwrb开源组件、pid开源算…...
一文看懂预训练和自训练模型
说到预训练模型,不得不提迁移学习了,由于很多数据不是标签数据,人工标注非常耗时,神经网络在很多场景下受到了限制。但是迁移学习和自学习的出现,在一定程度上缓解甚至解决了这个问题。我们可以在标签丰富的场景下进行…...
(五十四)大白话索引的页存储物理结构,是如何用B+树来实现的?.md
上一次我们给大家说了主键索引的目录结构,只要在一个主键索引里包含每个数据页跟他最小主键值,就可以组成一个索引目录,然后后续你查询主键值,就可以在目录里二分查找直接定位到那条数据所属的数据页,接着到数据页里二…...
前端Vue代码风格指南
一、命名规范 市面上常用的命名规范: camelCase(小驼峰式命名法 —— 首字母小写) PascalCase(大驼峰式命名法 —— 首字母大写) kebab-case(短横线连接式) Snake(下划线连接式&…...
「TCG 规范解读」基础设施架构和协议 (2)
可信计算组织(Ttrusted Computing Group,TCG)是一个非盈利的工业标准组织,它的宗旨是加强在相异计算机平台上的计算环境的安全性。TCG于2003年春成立,并采纳了由可信计算平台联盟(the Trusted Computing Platform Alli…...
NodeJs 中的 HTML 模板
💂 个人网站:【海拥】【摸鱼游戏】【神级源码资源网】🤟 前端学习课程:👉【28个案例趣学前端】【400个JS面试题】💅 想寻找共同学习交流、摸鱼划水的小伙伴,请点击【摸鱼学习交流群】 HTML 模板是一种允许我…...
3.ffmpeg命令行环境搭建、ffmpeg命令行初步了解
在上章,我们讲过: ffmpeg.exe: 主要用于转码或者剪切的应用程序, 也可以从url/现场音频/视频源抓取输入源ffplay.exe: 主要用于播放视频的应用程序,该应用程序源码是开源的,我们后面章节会去源码分析ffprobe.exe: 主要用于分析视频码流的应用程序, 可以获取媒体文件的详细信息,…...
Kubernetes初始化容器
初始化容器 之前了解了容器的健康检查的两个探针:liveness probe(存活探针)和readiness probe(可读性探针)的使用方法,我们说在这两个探针是可以影响容器的生命周期的,包括我们之前提到的容器的…...
leetcode: Swapping Nodes in a Linked List
leetcode: Swapping Nodes in a Linked List1. 题目描述2. 题目解答3. 总结1. 题目描述 You are given the head of a linked list, and an integer k.Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node f…...
Nydus 在约苗平台的容器镜像加速实践
文 | 向申 约苗平台运维工程师 关注云原生领域 本文字数 9574阅读时间24分钟 本文是来自向申同学的分享,介绍了其在 K8s 生产环境集群部署 Nydus 的相关实践。 Nydus 是蚂蚁集团,阿里云和字节等共建的开源容器镜像加速项目,是 CNCF Dragon…...
企业对不同形态CRM系统价格需求不同
很多企业在选型时关心CRM客户管理系统的价格,有人对CRM的价格完全没有概念,也有的人先问价格再看其他。CRM价格在系统选型中到底有多重要?不同类型CRM系统的价格是否有所不同? CRM的不同产品形态也会影响价格 通常情况下&#x…...
「JVM 高效并发」线程安全
面向过程编程,把数据和过程分别作为独立的部分考虑,数据代表问题空间中的客体,程序代码则用于处理这些数据;面向对象编程,把数据和行为都看做对象的一部分,以符合现实世界的思维方式来编写和组织程序&#…...
微信扫码登录
一、准备工作 微信开发者平台:https://open.weixin.qq.com 1、注册 2、邮箱激活 3、完善开发者资料 4、开发者资质认证:仅能企业注册(后面提供学习的使用渠道)准备营业执照,1-2个工作日审批、300元 5、创建网站应用&…...
Unity协程的简单应用
Unity协程是一种特殊的函数,可以让你在Unity中创建一种类似于多线程的异步操作。它可以在需要等待某个操作完成时,暂停执行当前代码,等待某个条件满足后再继续执行。 在一般情况下 unity中调用函数时,函数将运行到完成状态&#x…...
LeetCode 1250. Check If It Is a Good Array【数论】
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章…...
ETHDenver 2023
ETHDenver是全球最大、持续时间最长的以太坊活动之一,今年的活动定于2月24日至3月5日在美国科罗拉多州丹佛市盛大举行。这次活动将面向以太坊和其他区块链协议爱好者、设计者和开发人员。Moonbeam作为ETHDenver 2023的Meta赞助商,将在本次活动中展示令人…...
React架构演变
老版React架构 React 16之前的架构 其实就分为两个部分: Reconciler协调器Render渲染器 Reconciler协调器负责本次更新有什么组件需要被渲染,diff算法就发生在这个步骤中,在diff算法中会将上次更新的组件和本次更新的组件做一个对比&…...
安全认证--JWT介绍及使用
安全认证--JWT介绍及使用1.无状态登录原理1.1.什么是有状态?1.2.什么是无状态1.3.如何实现无状态1.4.JWT1.4.1.简介1.4.2.数据格式2.编写JWT工具2.1.添加JWT依赖2.2.载荷对象2.3.工具2.4.测试2.4.1.配置秘钥2.4.2.测试类1.无状态登录原理 有状态登录和无状态登录详…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释
以Module Federation 插件详为例,Webpack.config.js它可能的配置和含义如下: 前言 Module Federation 的Webpack.config.js核心配置包括: name filename(定义应用标识) remotes(引用远程模块࿰…...
从物理机到云原生:全面解析计算虚拟化技术的演进与应用
前言:我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM(Java Virtual Machine)让"一次编写,到处运行"成为可能。这个软件层面的虚拟化让我着迷,但直到后来接触VMware和Doc…...
