287. Find the Duplicate Number (1)

Link

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(n2).

4. There is only one duplicate number in the array, but it could be repeated more than once.

Solution

這個問題之前在Movial面試被問過，當初用realsum - sum(1~n) 的方法帶過，但實際上不能用。因為數字可能重複多次。(ex. 2,2,2,2,2)

第一個想法是用set 去做，但space complexity would be O(n)

方法二: (cycleing link)

因為nums裡的value會介於len-1~0之間, len為nums大小，所以可以用這個方法。

用兩個指標，根據nums裡的value值決定下一個點的位置，然後slow的一次改變一次位置, ie. slow = nums[slow];

fast一次會改變兩次ie. fast = nums[nums[fast]]

當slow = fast時，代表兩種不同速度的指標會合在同一個位置。表示有一個cycling出現。

接下來就是找到cycling的入口，也就是重複的點，根據以下推論:

m = xn -k; 所以當slow留在原地，fast重頭開始一起慢慢走，最後會合的就會是loop entry。

讓slow維持在原位置，fast回到起點(index=0)，slow與fast一起一步一步地走 看何時走到一起。那時就是起點。

目前只能先硬記結果了，應該很難現場想到

  public int findDuplicate(int[] nums) {
        int fast = 0, slow = 0;
        do{
            fast = nums[nums[fast]];
            slow = nums[slow];
        }while(fast != slow);
        
        fast = 0;
        while(fast != slow){
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }