Python different solutions with comments (bubble sort, selection sort, heap sort and quick sort).


  • 45
    C
    # O(nlgn) time
    def findKthLargest1(self, nums, k):
        return sorted(nums, reverse=True)[k-1]
        
    # O(nk) time, bubble sort idea, TLE
    def findKthLargest2(self, nums, k):
        for i in xrange(k):
            for j in xrange(len(nums)-i-1):
                if nums[j] > nums[j+1]:
                    # exchange elements, time consuming
                    nums[j], nums[j+1] = nums[j+1], nums[j]
        return nums[len(nums)-k]
        
    # O(nk) time, selection sort idea
    def findKthLargest3(self, nums, k):
        for i in xrange(len(nums), len(nums)-k, -1):
            tmp = 0
            for j in xrange(i):
                if nums[j] > nums[tmp]:
                    tmp = j
            nums[tmp], nums[i-1] = nums[i-1], nums[tmp]
        return nums[len(nums)-k]
        
    # O(k+(n-k)lgk) time, min-heap
    def findKthLargest4(self, nums, k):
        heap = []
        for num in nums:
            heapq.heappush(heap, num)
        for _ in xrange(len(nums)-k):
            heapq.heappop(heap)
        return heapq.heappop(heap)
    
    # O(k+(n-k)lgk) time, min-heap        
    def findKthLargest5(self, nums, k):
        return heapq.nlargest(k, nums)[k-1]
        
    # O(n) time, quick selection
    def findKthLargest(self, nums, k):
        # convert the kth largest to smallest
        return self.findKthSmallest(nums, len(nums)+1-k)
        
    def findKthSmallest(self, nums, k):
        if nums:
            pos = self.partition(nums, 0, len(nums)-1)
            if k > pos+1:
                return self.findKthSmallest(nums[pos+1:], k-pos-1)
            elif k < pos+1:
                return self.findKthSmallest(nums[:pos], k)
            else:
                return nums[pos]
     
    # choose the right-most element as pivot   
    def partition(self, nums, l, r):
        low = l
        while l < r:
            if nums[l] < nums[r]:
                nums[l], nums[low] = nums[low], nums[l]
                low += 1
            l += 1
        nums[low], nums[r] = nums[r], nums[low]
        return low

  • 6
    Y

    I don't know why the min-heap takes O(k+lgk(n-k)) time, someone could provide a better explanation on why O(k+lgk(n-k)) time ? thanks.

    Based on on this page: 'http://www.ardendertat.com/2011/05/30/my-favorite-interview-question/', I guess the time complexity of the heap sort should be: O(n) + (n - k) log (n) . O(n) for constructing the heap, n - k for poping out n - k smallest elements to obtain the k_{th} largest element, and log (n) for searching in heap.


  • 0
    C

    Hi, yuhangwu, O(k) is the time to build min-heap, after this process you have (n-k) elements left, every element needs to be inserted into the min-heap which costs log(k) time for each element, so the total time is O(k+(n-k)log(k)).


  • 0
    Y

    Hi Caikehe, thank you for your explanation. I agree this might be the case for 'findKthLargest5' (sorry I have not checked the source function whether the python update the heap on-the-fly). But for 'findKthLargest4', it seems to me that the code first constructs a whole heap with O(n), then output the elements from the heap.


  • 0
    D
    This post is deleted!

  • 0
    D
    This post is deleted!

  • 1
    G

    Hi caikehe! Thanks for the solutions. One note: the findKthLargest4 heap solution isn't O(k+(n-k)lgk). You are pushing all the elements into the heap, that is already O(nlogn). I guess you mixed it with another answer of yours https://leetcode.com/discuss/61586/python-heap-quick-partition-solutions-nlogn-complexities


  • 3
    W

    for the first solution, you don't need reverse=True, you can just do this:
    sorted(nums)[-k]


  • 1

    I trie quick selection but it took about 3000ms. Then I changed it to pick up a random element as pivot instead of the right-most one and it only took 59ms.

    from random import randint
    class Solution(object):
        def findKthLargest(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: int
            """
            def partition(l, r):
                ri = randint(l, r)
                nums[r], nums[ri] = nums[ri], nums[r]
                for i, v in enumerate(nums[l: r+1], l):
                    if v >= nums[r]:
                        nums[l], nums[i] = nums[i], nums[l]
                        l += 1
                return l - 1
            
            l, r, k = 0, len(nums) - 1, k - 1
            while True:
                pos = partition(l, r)
                if pos < k:
                    l = pos + 1
                elif pos > k:
                    r = pos - 1
                else:
                    return nums[pos]
    

  • 0
    P

    Can someone explain why I get TLE with this?

    thanks

    class Solution(object):
        def findKthLargest(self, nums, k):
    
            k = len(nums) - k
            lo = 0
            hi = len(nums)-1
            while lo < hi:
                j = self.partition(nums, lo, hi)
                if j < k:
                    lo = j + 1
                elif j > k:
                    hi = j - 1
                else:
                    break
            return nums[k]
    
        def partition(self, array, lo, hi):
            i = lo
            j = hi
            while True:
                while i < hi and array[i] < array[lo]:
                    i += 1
                while j > lo and array[lo] <= array[j]:
                    j -= 1
                if i >= j:
                    break
                array[i], array[j] = array[j], array[i]
    
            array[lo], array[j] = array[j], array[lo]
            return j
    

  • 0
    S

    run more bubble sort soln, you get it accepted and beat 0.1%


Log in to reply
 

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