Python constant extra space and guarantee average O(n)


  • 1
    S
    
    class Solution(object):
        def findKthLargest(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: int
            """
            s, e = 0, len(nums)-1
            while s <= e:
                rand = random.randint(s, e)
                nums[rand], nums[e] = nums[e], nums[rand]
                i = s
                for j in range(s, e):
                    if nums[j] > nums[e]:
                        nums[i], nums[j] = nums[j], nums[i]
                        i+=1
                nums[i], nums[e] = nums[e], nums[i]
                if i == k-1:
                    return nums[i]
                elif i < k-1:
                    s = i+1
                    k-=(i-s+1)
                else:
                    e = i-1
            return -1
    
    

Log in to reply
 

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