My easy understanding Java solution, just like linkedList


  • 0
    D

    This problem is very funny, we can see it as a linkedList with a loop, find the duplicate one is like find the loop head.
    So we can use fast and slow pointer to handle it.
    For example:
    2-9-1-5-3-6-8-7-9..... , 9 is the loop head, but slow and fast meets at 7, so we can set another newSlow, and goes one step with slow, until meets each other.

     public int findDuplicate(int[] nums) {
            int slow = nums[0], fast = nums[0];
            while (true) {
                slow = nums[slow];
                fast = nums[nums[fast]];
                if (slow == fast) {
                    break;
                }
            }
            int newSlow = nums[0];
            while (newSlow != slow) {
                newSlow = nums[newSlow];
                slow = nums[slow];
            }
            return slow;
        }
    

Log in to reply
 

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