Python 40-50ms solution sharing and explain, not binary search or two pointer


  • -4
    O
    def findDuplicate(self, nums):
        """
        Swap based on the last element! and swap it with element in lastVal - 1! 
        1 2 3 1 => find duplicate
        ^     ^
        2 1 3 1 => 1 1 3 2 => 1 2 3 1 => find duplicate
        ^     ^      ^   ^    ^     ^  
        worst cast: swap n times
        2 3 1 1 => 1 3 1 2 => 1 2 1 3 => 1 2 3 1
        ^     ^      ^   ^        ^ ^          ^
        """
        count = 1
        while count <= len(nums):
            lastVal, count = nums[-1], count + 1
            if lastVal == nums[lastVal-1]:
                return nums[-1]
            nums[-1], nums[lastVal-1] = nums[lastVal-1], nums[-1]
        return nums[-1]

  • 1
    R

    You must not modify the array (assume the array is read only).

    You solution modified the array.


Log in to reply
 

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