LeetCode 287. Find the Duplicate Number
LeetCode 287. Find the Duplicate Number
ShenduCC
发布于 2020-05-22 16:06:09
发布于 2020-05-22 16:06:09
一道好题目。 发现数组里重复的数字是什么，不借助额外的数据结构。数组里的数字范围是1-n,数组的个数是n+1,所以一定存在重复的情况。重复的个数至少是1。如果题目说只有一个数字是重复的，那么就是另一道题目了。
首先根据这个数组的特性，按照数组的下标把从第0个数开始，把数组变成一个链表，链表的next的指向下标为当前值value的数组元素，这样的链表是一定会有环的，数组里的元素也并不会都出现再链表中。 一定有环是因为，有重复的数字，所以链表肯定会指向之前的某个节点。
那个节点就是我们要求的重复的数字。
怎么去求一个链表的环其实节点，我们用两个指针，一个慢指针，一个快指针。慢指针走一步，快指针走两步。从起点出发，如果两个指针指向相同的节点，说明快指针当前走的路程是慢指针的两倍，而且两者相遇了，然后从起点开始再走一个慢指针，同时先前的慢指针也开始走，然后两者相遇的节点就是环的起始节点。这是可以证明的，画个图，就可以证明出来了。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slower=0;
int faster=0;
do
{
slower = nums[slower];
faster = nums[nums[faster]];
}
while(slower != faster);
int start = 0;
while(start!=slower)
{
start = nums[start];
slower = nums[slower];
}
return start;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-05-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读