Share my solution O(N) time O(1) space. 12 ms


  • 55
    M
    class Solution {
    public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0;
    	int fast = 0;
    	int finder = 0;
    
    	while (true)
    	{
    		slow = nums[slow];
    		fast = nums[nums[fast]];
    
    		if (slow == fast)
    			break;
    	}
    	while (true)
    	{
    		slow = nums[slow];
    		finder = nums[finder];
    		if (slow == finder)
    			return slow;
    	}
    }
    

    };


  • 4
    L

    I think your solution is very awesome, but I am a little confused.

    Can you explain the results of the two loops?

    Thank you


  • 2
    K

    This approach essentially creates a graph out of the array (outgoing edge from each array value to the index denoted by that array value). Then, you run Floyd's cycle finding algorithm (tortoise and hare) to find the cycle (duplicate value in array). Look up Floyd's cycle finding algorithm for more info!


  • -6
    B

    Is this O(1) space? I think it's O(n) right? Otherwise it's O(n) time

    public class Solution {
    public int findDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < nums.length; i++){
            if(set.contains(nums[i])){
                return nums[i];
            }else{
                set.add(nums[i]);
            }
        }
        return -1;
    }
    }

  • 0
    T

    Yes, in worst case scenario, it is O(n) extra space


  • 0
    Q

    I don't think the code is right. let us have an array {0,1,2,2,3}. Both fast and slow will be 0 and never move.


  • 0
    A

    the problem states the input is between 1 and n. 0 is not valid.


  • 0
    Z

    what if nums[0]=n, is it supposed to be over the boundary?


  • 0
    T

    nums containing n + 1 integers


  • 0
    C

    @manul89 how about the testcase [4,5,5]


  • 0
    K

    @CHIX Thats not a valid input. You have n+1=3, so the maximum value you can have in the array is 2.


  • 5

    So impressive solution. Share my explanation as below

    0_1474620685029_Screen Shot 2016-09-23 at 4.50.28 PM.png

    k is the length before entering circle,
    c is the length of circle
    A is the point to enter circle

    When fast and slow meets, let the distance moved by slow be X
    Then X = 2X-X = n*c where n is an integer and n*c>=k

    So the meeting point of fast and slow has a offset (n*c-k)%c to point A

    To let slow reach point A we need slow to go another k points, so that (n*c-k+k)%c=0

    When finder goes from start point to A, the distance is k, slow goes the same distance, and we get the entrance of the circle.

    The entrance of circle has more than one in-pointers, this means at least two numbers at different indices in the array have same value, the index of slow and finder is the duplicate number.


  • 1
    W

    follow up: what if there are multiple duplicates, how to find them all?


  • 5
    X

    @manul89
    发一段中文的解释,假设数组中没有重复,那我们可以做到这么一点,就是将数组的下标和1到n每一个数一对一的映射起来。比如数组是213,则映射关系为0->2, 1->1, 2->3。假设这个一对一映射关系是一个函数f(n),其中n是下标,f(n)是映射到的数。如果我们从下标为0出发,根据这个函数计算出一个值,以这个值为新的下标,再用这个函数计算,以此类推,直到下标超界。实际上可以产生一个类似链表一样的序列。比如在这个例子中有两个下标的序列,0->2->3。
    但如果有重复的话,这中间就会产生多对一的映射,比如数组2131,则映射关系为0->2, {1,3}->1, 2->3。这样,我们推演的序列就一定会有环路了,这里下标的序列是0->2->3->1->1->1->1->...,而环的起点就是重复的数。


  • 0
    X

    @wayne5 Good Question, so what's your idea?


  • 0
    L
    This post is deleted!

  • 0
    S

    @xiaowu4
    Good Answer

    Without any node points to nums[0], nums[0] becomes a head of a linked list (list0) , which contains a subset (set0) of all n+1 nodes.
    Suppose list0 has no cycle.
    Let k=card of set0, list0 has k nodes and k pointers. Each of these k pointer points to a node in set0-{nums[0]}, whose cardinality is k-1, by Pigeonhole Principle there are at least two pointers point to one node. This leads to a contradiction.
    So if there exists a cycle, it should be reached from nums[0].


Log in to reply
 

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