当前位置: 首页 > news >正文

287. 寻找重复数

问题

给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1:
输入:nums = [1,3,4,2,2]
输出:2

示例 2:
输入:nums = [3,1,3,4,2]
输出:3

分析

Floyd 判圈算法.

假设环长为 L,从起点到环的入口的步数是 a,从环的入口继续走 b 步到达相遇位置,从相遇位置继续走 c 步回到环的入口,则有 b+c=L,其中 L、a、b、c 都是正整数。根据上述定义,慢指针走了 a+b 步,快指针走了 2(a+b) 步。从另一个角度考虑,在相遇位置,快指针比慢指针多走了若干圈,因此快指针走的步数还可以表示成 a+b+kL,其中 k 表示快指针在环上走的圈数。

代码

http://www.hskmm.com/?act=detail&tid=23123

相关文章:

  • 福州市 2025 国庆集训 Day2 前三题题解
  • 2025 年马赛克厂家 TOP 企业品牌推荐排行榜,陶瓷,游泳池,喷墨,冰裂,拼花,防滑,复古,家装马赛克推荐这十家公司!
  • oppoR9m刷Linux系统: 手动备份系统与基带IMEI/NVRAM/QCN
  • 原来你是这样的claude code aciton:没想象中好
  • 实用指南:【Python】正则表达式
  • FlareOn1 -- 5get_it
  • 2025 年阀门厂家 TOP 企业品牌推荐排行榜,管道阀门,气动,调节,电动执行器,生产,电磁,不锈钢,进口,耐高温阀门推荐这十家公司
  • 深入解析:Ceph 分布式存储学习笔记(二):池管理、认证和授权管理与集群配置(下)
  • tcp与udp 协议 - 摘星
  • 赛前训练4 extra 字典树
  • CF1450E Capitalism
  • 二分图最大匹配 匈牙利算法
  • 2025 年脱硫剂厂家 TOP 企业品牌推荐排行榜,氧化铁,羟基氧化铁,常温氧化铁,沼气,天然气,煤气,煤层气,液化气,二氧化碳,氨气脱硫剂公司推荐
  • 2025 年砝码厂家 TOP 企业品牌推荐排行榜,不锈钢,标准,校准,天平,无磁,锁型,蓬莱,铸铁,定制,单双钩砝码公司推荐!
  • Java 在Word 文档中添加批注:高效文档协作的利器 - 指南
  • 2025雨棚生产厂家 TOP 企业品牌推荐排行榜,西安,陕西,西北推拉雨棚,推拉,移动,活动,户外,电动伸缩雨棚推荐这十家公司!
  • 关于整除分块
  • 2025 年木工机械设备厂家 TOP 企业品牌推荐排行榜,深度剖析木工机械设备推荐这十家公司!
  • Python语言自动玩游戏的消消乐游戏程序代码3QZQ
  • Python语言自动玩游戏的数字拼图游戏程序代码ZXQMQZQ
  • 如何找出集合的两个子集使得和相等?
  • Python语言自动玩游戏的俄罗斯方块游戏程序代码QZQ
  • Spring AI(七)Spring AI 的RAG搭建集合火山向量模型+阿里云Tair(企业版)
  • Python语言自动玩游戏的数字拼图游戏程序代码QZQ
  • 赛前训练4 字符串哈希
  • 英语
  • 处处吻
  • ThreadLocal原理与使用详解
  • WinCC监控框架实战解析:打通物联网网关的关键步骤
  • 2025国庆Day1