O(nlogn) and O(n) solutions in C++, well-explained


  • 1

    The first solution is quite intuitive which I think it's easy for you guys to understand.

    As for the second, the numbers' range is [1...n] while the array is n+1 long which means all the numbers can be the index of the array except for the 0, then let's start from index 0 and follow its number to traverse the array, but soon we'll find out that we cannot leave the array any more (since all the numbers are pointing to index [1...n], then there must be duplicates to form a circle here.

    Finding the circle is done, then how about finding the entry of the circle, which is also the duplicate (two numbers pointing to the same index).

    There is a classic problem in linked list, we will do it as it does. If you just do not know that, check this post first. Good luck!


    class Solution {
    public:
        //Binary search - amazing;
    	int findDuplicate(vector<int>& nums) 
    	{
            int l = 1, h = nums.size()-1;
            while(l < h)
            {
                int count = 0;
                int m = (h+l)/2;
                for(int i = 0; i < nums.size(); ++i)
                    if(nums[i]>=l && nums[i]<=m) count++;
                if(count <= m-l+1) l = m+1;
                else h = m;
            }
            return l;
        }
    
    	//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(vector<int>& nums) {
            int slow = nums[0], fast = nums[nums[0]];
            while(slow != fast)
            {
                slow = nums[slow];
                fast = nums[nums[fast]];
            }
            fast = 0;
            while(fast != slow)//find the start of the loop which means at least two integer are the same value;
            {
                slow = nums[slow];
                fast = nums[fast];
            }
            return slow;
        }
    };

Log in to reply
 

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