solution with explanation


  • 0
    V
    public class Solution {
        public int findDuplicate(int[] nums) {
            int slow = nums[0];
            int fast = nums[nums[0]];
            // mu --- first node of repetition
            // lam --- length of the loop
            while (slow != fast) {  //x_{i} = x_{2i} = x_{i + k * lam} ==> i = k * lam
                slow = nums[slow];
                fast = nums[nums[fast]];
            }
            
            slow = 0;
            // slow is at x_{0}, fast is at x_{k * lam}
            // x_{j} = x_{j + k * lam}  ==> j = mu for any j >= mu
            while (slow != fast) {
                slow = nums[slow];
                fast = nums[fast];
            }
            // slow and fast are both at mu
            return slow;
        }
    }
    

    This page gives a quite clear explanation of the Floyd's cycle-detection algorithm. Here is the principal:

    • The position where the two pointers meet must satisfy this relation: x_{i} = x_{i + k * lambda} where x_{i} is the position representation for the slower pointer and x_{i + k * lambda} is the position representation for the faster pointer. k is a constant and lambda is the length of the loop.
    • When the speed of the faster pointer is twice of the speed of the slower (that is, i + k * lambda = 2i), i = k * lambda. This indicates that slower and faster pointers meet at a k * lambda away from the origin, denote this distance as v. That is, v = k * lambda.
    • After knowing v. We relocate two pointers, one at origin and the other at v. That is, they are v apart. Move them with the same speed. So one is at x_{j} and the other is at x_{j + v}. Remember v = k * lambda, x_{j} = x_{j + k *lambda} for any j >= mu, where mu is the entry point of the loop (i.e. they are constant cycles apart).

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.