[Day 25] Leetcode 287. Find the Duplicate Number (C++)

前言

今天先暂停一下sum的题目，来做top 100 liked的另外一题─287. Find the Duplicate Number。

想法

这题其实光是官方解答就非常精彩~ 提供了7种解法。其实这题如果没有特别限制的话，非常简单。不过题目同时设下了三个限制就让可行的方式少了很多：

1. constant space=> 空间复杂度 O(1)
2. without modifying the array nums
3. linear time=> 时间复杂度 O(n)
   虽然第三个是额外挑战啦~ 没有写在题目正文中。
   如果没有这些限制的话，可以用一个set来记录看过的，遇到有看过的就回传，遍历一次就可完成，但空间复杂度会是O(n)；或者经过sort排列，这样一样的数字就会排在隔壁，然後再遍历一次看前後有没有相同的，但这样会更改到原本的array，且时间复杂度为O(nlogn)；或者是利用题目说出现的数字会在1~n之间的特性，把出现数字做为index，去把那位数更改成负的，这样下次遇到发现有负数的话就代表该数字被改过了，不过这也违反不能modify原本array的限制。
   最後官方提供的解答中，最後只有一种方式符合题目的三项规定：

Floyd's Tortoise and Hare (Cycle Detection)

我们直接来看解答，再来分析这个解法的想法：

class Solution {
public:
    int findDuplicate(vector<int>& nums) {

        // Find the intersection point of the two runners.
        int tortoise = nums[0];
        int hare = nums[0];

        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        } while (tortoise != hare);

        // Find the "entrance" to the cycle.
        tortoise = nums[0];
        while (tortoise != hare) {
            tortoise = nums[tortoise];
            hare = nums[hare];
        }

        return hare;
    }
};

它是利用cycle detection的概念，其实跟142. Linked List Cycle II这题的概念有关。这个解答的变数命名有点生动XD
简单来说，它把这题当成有点linked list的概念，因为它限制nums[i]的值都会在1~nums.size()-1之间，那就必定可以找到一个nums[nums[i]]的值，我们就把它当成是一个next指标，指到它存在的地方的值。那我们接下来就用"快慢指针法"(解法叫龟兔赛跑法)，总之，就让快的那个走的速度是慢的两倍快，至於它怎麽走？就是按照linked list next的位置去走。那如果有重复的数字出现，代表会有两个(或更多)的数字会走到同一个点，然後就会重复该点的动作，进入一个回圈。
进入回圈代表什麽呢？代表快指针会碰得到慢指针。而当它碰到的时候，我们就可以来计算回圈的起始点=重复点了。
此时就让一个从起点重新出发，一个从目前的碰头点出发，再次碰到的时候就是回圈起始点了。
如果还有疑问的话，也可以到官方解答去看图片详解。
不如明天就来详解142. Linked List Cycle II这题概念吧！

结语

话说，这题限制那麽多，根本是hard。solution 1~7已经各种技巧都出来了，可以再去官方解那边慢慢看~
接戏来再回归sum系列题目挑战~