Share my Python solution with QuickSelect idea


  • 15
    Y
    class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {integer}
    def findKthLargest(self, nums, k):
        # QuickSelect idea: AC in 52 ms
        # ---------------------------
        #
        pivot = nums[0]
        left  = [l for l in nums if l < pivot]
        equal = [e for e in nums if e == pivot]
        right = [r for r in nums if r > pivot]
    
        if k <= len(right):
            return self.findKthLargest(right, k)
        elif (k - len(right)) <= len(equal):
            return equal[0]
        else:
            return self.findKthLargest(left, k - len(right) - len(equal))

  • 0
    L

    what is the time complexity? Is it O(n) guaranteed?


  • 0
    C

    Nice solution. But you should consider choosing other pivot. Using pivot = nums[0] would be slow if nums is already sorted. pivot = nums[len(nums)//2] seems to be a good choice for this problem


  • 2
    5

    @ymcagodme honestly it's not so good because it use too much memory.


  • 0
    L

    @57322741 Minor improvement, but I agree this uses too much memory

    def findKthLargest( nums, k):
        # QuickSelect idea: AC in 52 ms
        # ---------------------------
        #
        pivot = nums[0]
        left  = []
        equal = []
        right = []
        for i in nums:
            if i<pivot:
                left.append(i)
            elif i==pivot:
                equal.append(i)
            else:
                right.append(i)
        if k <= len(right):
            return findKthLargest(right, k)
        elif (k - len(right)) <= len(equal):
            return equal[0]
        else:
            return findKthLargest(left, k - len(right) - len(equal))

  • 0
    A

    @livelearn I think this will take the exact same memory as the solution?


  • 0
    L

    @adit6 No, there are better solutions that have O(1) memory


  • 1
    L

    random.shuffle(nums)
    We have to add shuffle before picking the first element as pivot, otherwise the worse case can not pass.


Log in to reply
 

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