Three different solutions from worst to best in C, well-commented


  • 6

    The first solution is quite intuitive and direct but it's not the answer since it will cost another extra O(n) space which is not allowed by the problem. But it's quite simple and easy-understanding, so here it is.


    //AC - 8ms - using linear space;
    int findDuplicate(int* nums, int size)
    {
        int* arr = (int*)malloc(sizeof(int)*size);
        memset(arr, 0, sizeof(int)*size);
        for(int i = 0; i < size; i++)
        {
            arr[nums[i]]++;
            if(arr[nums[i]] > 1)
                return nums[i];
        }
        return 0;
    }
    

    The second solution is to use binary search to search the duplicate considering pigeon hole rule which is quite direct in this case. [1, n] inclusive in the array whose index ranges from [0, n] inclusive, so counting the number less than or equal to the middle can accelerate the searching process.

    //nlogn time cost and constant space cost;
    int findDuplicate(int* nums, int size)
    {
        int l=1, h=size-1;
        while(l < h)
        {
            int m = (l+h)/2;
            int count = 0;
            for(int i = 0; i < size; i++)
                if(nums[i]>=l && nums[i]<=m) count++;
            if(count <= m-l+1) l = m+1;
            else h = m;
        }
        return l;
    }
    

    The last solution is quite awesome adopting the feature of the linked list in this condition. Reading the comments can be enough to understand the whole thread.

    //AC - 4ms - using constant space and linear time;
    //similar to find the start of the loop in a linked list;
    //the integer is the pointer while the index is the link;
    int findDuplicate(int* nums, int size)
    {
        if(size > 0)
        {
            int slow = nums[0];
            int fast = nums[nums[0]];
            while(slow != fast) //check the existence of the loop;
            {
                slow = nums[slow];
                fast = nums[nums[fast]];
            }
            fast = 0;
            while(slow != fast) //find the start of the loop which means at least two integer are the same value;
            {
                slow = nums[slow];
                fast = nums[fast];
            }
            return slow;
        }
        return -1;
    }

  • 0
    T

    Nice solution!


  • 0
    D

    Can you explain the binary search algorithm


  • 1

    In binary search, we always chop off the other half which doesn't meet the requirements. In this case, we are searching for the duplicate then if we are sure that there is no chance the duplicate lies in the other half then we can cut it off. We searched through the whole array to count how many numbers lies in [l, m] (l, l+1, ..., m there are at least m-l+1 distinct numbers in that range, so we if there is duplicate there, the count should at least m-l+1) but if the count <= m-l+1 then there is no chance the duplicate lies in [l, m] so we move to the other half by setting l=m+1. Good luck.


  • 0
    Q

    @LHearen
    , for "here are at least l-m+1 distinct numbers" I think you mean m-l+1, right?


  • 0

    @quesder Yes, sorry about that wrong typing sometimes....


  • 1
    B

    very good solution.


Log in to reply
 

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