O(nlogn) solution


  • 1
    S
    var findDuplicate = function(nums) {
    
        var anchor = Math.ceil(nums.length/2);
        var left =0;
        var right = nums.length;
        while(left<right)
        {
            var leftCount=0;
            var rightCount=0;
            var anchorCount=0;
            for(var i=0;i<nums.length;i++)
            {
                if(nums[i]=== anchor)
                {
                    anchorCount++;
                    if(anchorCount>1)
                    {
                        return anchor;
                    }
                }
                
                else if(nums[i]<anchor && nums[i]>=left)
                    leftCount++;
                else if(nums[i]<=right && nums[i]>=left)
                    rightCount++;
            }
            if(leftCount>rightCount)
                {
                    right = anchor;
                }
                else
                {
                    left = anchor;
                }
                    anchor =left+ Math.ceil((right-left)/2);
        }
        
        return right;
    };
    

  • 0
    W

    @Samehegazy thanks for sharing


Log in to reply
 

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