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

  • 45
    # 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):
        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)
                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

    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: '', 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

    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

    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
    This post is deleted!

  • 0
    This post is deleted!

  • 1

    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

  • 3

    for the first solution, you don't need reverse=True, you can just do this:

  • 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
                    return nums[pos]

  • 0

    Can someone explain why I get TLE with this?


    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
            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:
                array[i], array[j] = array[j], array[i]
            array[lo], array[j] = array[j], array[lo]
            return j

  • 0

    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.