Share my Python solution with QuickSelect idea


  • 12
    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


Log in to reply
 

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