当前位置:网站首页>287. 寻找重复数-快慢指针
287. 寻找重复数-快慢指针
2022-07-05 08:31:00 【Mr Gao】
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
对于这题
首先,可以使用快慢指针找换
如果存在换,那么快慢指针会在环内相遇,但是相遇的点,不一定是换的起点
将快指针放回head,快慢指针以相同的步进移动,最终,会在环的入口相遇
你吹过我来时的风,我回到故乡,竟再次在原点相遇
int findDuplicate(int* nums, int numsSize) {
int fast = 0;
int slow = 0;
while (true) {
fast = nums[nums[fast]];
slow = nums[slow];
if (fast == slow) {
fast = 0;
while (fast != slow) {
fast = nums[fast];
slow = nums[slow];
}
return slow;
}
}
}
边栏推荐
- 动力电池UL2580测试项目包括哪些
- Slist of linked list
- Management and use of DokuWiki
- STM32---IIC
- Example 008: 99 multiplication table
- Classic application of MOS transistor circuit design (2) - switch circuit design
- [trio basic tutorial 17 from getting started to mastering] set up and connect the trio motion controller and input the activation code
- STM32 --- configuration of external interrupt
- L298N module use
- Brief discussion on Buck buck circuit
猜你喜欢
More than 90% of hardware engineers will encounter problems when MOS tubes are burned out!
实例009:暂停一秒输出
MATLAB小技巧(28)模糊綜合評價
剑指 Offer 06. 从尾到头打印链表
Management and use of DokuWiki (supplementary)
leetcode - 445. 两数相加 II
Management and use of DokuWiki
如何写Cover Letter?
MATLAB skills (28) Fuzzy Comprehensive Evaluation
How to copy formatted notepad++ text?
随机推荐
List of linked lists
Example 005: three numbers sorting input three integers x, y, Z, please output these three numbers from small to large.
MHA High available Cluster for MySQL
每日一题——输入一个日期,输出它是该年的第几天
Design a clock frequency division circuit that can be switched arbitrarily
实例004:这天第几天 输入某年某月某日,判断这一天是这一年的第几天?
Detailed explanation of SQL server stored procedures
STM32 summary (HAL Library) - DHT11 temperature sensor (intelligent safety assisted driving system)
Arduino uses nrf24l01+ communication
Various types of questions judged by prime numbers within 100 (C language)
Cinq détails de conception du régulateur de tension linéaire
Lori remote control commissioning record
Simple design description of MIC circuit of ECM mobile phone
Arduino+a4988 control stepper motor
Esphone retrofits old fans
Bluebridge cup internet of things basic graphic tutorial - GPIO input key control LD5 on and off
STM32 single chip microcomputer - bit band operation
Example 006: Fibonacci series
Installation and use of libjpeg and ligpng
Classic application of MOS transistor circuit design (2) - switch circuit design