O(N) without extra space & without modifying the array


  • 13
    C
    //Basically transfer the problem to finding the beginning of cycle in linked list.     
    public int findDuplicate(int[] nums) {
                if(nums.length ==0 )
                    return 0;
                int slow=0, fast=0;
                slow = nums[slow];
                fast = nums[nums[fast]];
                while(slow != fast){
                    if(slow == nums[slow])
                        return slow;
                    slow = nums[slow];
                    fast = nums[nums[fast]];
                }
                fast = 0;
                while(slow != fast){
                    if(slow == nums[slow])
                        return slow;
                    slow = nums[slow];
                    fast = nums[fast];
                }
                return slow;
            }

  • 0
    C

    //Can be further simplified.

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

  • 0
    L

    for example, [0,1,1,2], what should your code return? you will return 0, but the ans should be 1.


  • 0
    L

    there will be no 0 in the problem


  • 0
    T

    genius idea!


  • 0
    C

    good idea. what we need to find is the node which is the previous node of the node which is the entrance of the ring.

    int FindDuplicateNumber::findDuplicateCyclicList(vector<int> &nums) {
    if(nums.size() ==0 )
    return 0;
    int slow =0;
    int fast =0;
    slow = nums[slow];
    fast = nums[nums[fast]];
    while(slow != fast){
    slow = nums[slow];
    fast = nums[nums[fast]];
    }
    int iDesiredLatter = slow;
    while (nums[slow] != iDesiredLatter){
    slow = nums[slow];
    }
    return slow;
    }


  • 0
    C

    good idea. what we need to find is the node which is the previous node of the node which is the entrance of the ring.


  • 0
    C

    Oh I was wrong. I have to start from original point.


  • 0
    C

    Oh I was wrong. I have to start from original point.


  • 0
    W

    simply genius...


  • 0
    I

    each integer is between 1 and n (inclusive)


Log in to reply
 

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