当前位置:网站首页>287. Looking for repeats - fast and slow pointer
287. Looking for repeats - fast and slow pointer
2022-07-05 08:35:00 【Mr Gao】
287. Look for repetitions
Given an inclusion n + 1 Array of integers nums , The numbers are all in [1, n] Within the scope of ( Include 1 and n), We know that there is at least one duplicate integer .
hypothesis nums Only A repeated integer , return The number of repetitions .
The solution you design must Don't modify Array nums And only constant level O(1) Extra space .
Example 1:
Input :nums = [1,3,4,2,2]
Output :2
Example 2:
Input :nums = [3,1,3,4,2]
Output :3
For this question
First , You can use the fast and slow pointer to find and change
If there is a change , Then the fast and slow pointers will meet in the ring , But the point of meeting , Not necessarily the starting point of change
Put the fast pointer back head, The speed pointer moves in the same step , Final , Will meet at the entrance of the ring
You blew the wind when I came , I returned to my hometown , Unexpectedly, we met again at the origin
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;
}
}
}
边栏推荐
- Run菜单解析
- MySQL MHA high availability cluster
- Arduino+a4988 control stepper motor
- Run menu analysis
- Detailed summary of FIO test hard disk performance parameters and examples (with source code)
- Various types of questions judged by prime numbers within 100 (C language)
- How apaas is applied in different organizational structures
- 287. 寻找重复数-快慢指针
- How can fresh students write resumes to attract HR and interviewers
- Speech recognition learning summary
猜你喜欢
随机推荐
Bluebridge cup internet of things competition basic graphic tutorial - clock selection
2022.7.4-----leetcode.1200
One question per day - replace spaces
PIP installation
The first week of summer vacation
猜谜语啦(9)
猜谜语啦(142)
Summary of SIM card circuit knowledge
Sword finger offer 05 Replace spaces
实例007:copy 将一个列表的数据复制到另一个列表中。
Negative pressure generation of buck-boost circuit
MySQL之MHA高可用集群
Xrosstools tool installation for X-Series
Run菜单解析
实例006:斐波那契数列
Take you to understand the working principle of lithium battery protection board
STM32 single chip microcomputer - bit band operation
STM32 lights up the 1.8-inch screen under Arduino IDE
STM32 summary (HAL Library) - DHT11 temperature sensor (intelligent safety assisted driving system)
NTC thermistor application - temperature measurement