【Leetcode】287. Find the Duplicate Number（查找数组中唯一一组相同数字）（单链表判环）

红太狼 2022-01-11 03:33 179阅读 0赞

Given an array *nums* containing *n* \+ 1 integers where each integer is between 1 and *n* (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

**Example 1:**

Input: [1,3,4,2,2]
    Output: 2

**Example 2:**

Input: [3,1,3,4,2]
    Output: 3

**Note:**

1.  You **must not** modify the array (assume the array is read only).
2.  You must use only constant, *O*(1) extra space.
3.  Your runtime complexity should be less than *O*(*n*2).
4.  There is only one duplicate number in the array, but it could be repeated more than once.

题目大意：

给出一个数组其中只包含从1~n的数据，数组包含了1+n个数据，我们需要从这个数组中找出唯一一组重复的数据。这个重复的数据至少会出现两次（还会有更多）。

解题思路：

**引入概念，单链表判环：**

**我们可以想象一下在一个环形跑道上，两个人的追击问题。如果两个人从同一点出发以不同的速度向同一个方向前进，那么可以得出在这个环上的某一个位置，这两个人会相遇。**

**综上所述，我们可以拓展到链表当中，令其中一个点的速度为d1=d1->next，而另一个的速度为d2 = d2->next->next，如果这个链表中存在环，那么在循环之后存在一个时刻，d1和d2会在某一点相遇，即链表存在环。**

从题目中我们可以发现，数据的范围都包含在数组的索引内。所以可以将数据的大小看做数据索引的一部分。

（未完待续）

class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            int tortoise = nums[0];
            int hare = nums[0];
            
            do{
                
                tortoise = nums[tortoise];
                hare = nums[nums[hare]];
                
            }while(tortoise != hare);
            
            int pos1 = tortoise;
            int pos2 = nums[0];
            while(pos1 != pos2){
                pos1 = nums[pos1];
                pos2 = nums[pos2];
            }
            return pos1;
        }
    };