leetcode

Kth Largest Element in an Array

Kth Largest Element in an Array

sort solution - # O(nlgn) time 28ms

1
2
3
4
5
6
7
8
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return sorted(nums, reverse=True)[k-1]

heapq solution - # O(k+(n-k)lgk) time, min-heap 28ms

1
2
3
4
5
6
7
8
9
import heapq
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return heapq.nlargest(k, nums)[k-1]

test code

1
2
3
4
5
6
7
8
In [393]: nums= [3,2,3,1,2,4,5,5,6]
In [394]: k = 4
In [396]: s = Solution(); t = s.findKthLargest(nums, k)
In [397]: t
Out[397]: 4

ref

heapq

1
2
3
4
5
6
7
8
9
10
11
12
13
In [405]: import heapq
In [406]: heapq.nlargest(k, nums)
Out[406]: [6, 5, 5, 4]
In [407]: heapq.nlargest?
Signature: heapq.nlargest(n, iterable, key=None)
Docstring:
Find the n largest elements in a dataset.
Equivalent to:  sorted(iterable, key=key, reverse=True)[:n]
File:      /System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/heapq.py
Type:      function

leet code