Simple 5 line Python solution using binary search


  • 6
    S

    The idea is that if you have a number (e.g. 5) and there are 5 numbers in the array that are less than or equal to 5 then the duplicate has to be a number greater than 5. Otherwise, by the pigeonhole principle the duplicate has to be one of the numbers between 1 and 5 inclusive.

    class Solution(object):
        def findDuplicate(self, nums):
            left, right = 1, len(nums)-1
            while left < right:
               mid = (right + left)/2
               left, right = [left, mid] if sum(i <= mid for i in nums) > mid else [mid+1, right]
            return right

  • 0
    S

    Haha! You beat me to it! :)


  • 0

    but,your program has a serious defection,For example: when the test case is =[1, 2, 3, 4, 5, 6, 7, 7 , 8, 9]

    your output is 7.5


  • 0
    class Solution(object):
        def findDuplicate(self, nums):
            left, right = 1, len(nums) - 1
            while left < right:
                mid = (right + left) / 2
                left, right = [left, mid] if sum(i <= mid for i in nums) > mid else [mid + 1, right]
            return right
    
    
            
    nums = [1, 2, 3, 4, 5, 6, 7, 7 , 8, 9]
    my = Solution()
    print(my.findDuplicate(nums))
    

  • 0
    S

    Is it possible you are using Python 3 for your test? In that case the single '/' represents floating point division rather than integer division as in Python 2.


  • 0
    S

    Is it possible you are using Python 3 for your test? In that case the single '/' represents floating point division rather than integer division as in Python 2.


  • 0
    S

    Does the problem assume that the array is in increasing order? What if it's not?


  • 0
    S

    it doe NOT assume the arry is in increasing order. the key thing to notice here is that even though the correct mid number between 1-n is done through binary search, the actual counting process goes through the entire range each time which is why the solution is log(n) * n (for each counting process)


  • 0

    it is so hard to come up with this idea


Log in to reply
 

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