# O(nlgn) time
def findKthLargest1(self, nums, k):
return sorted(nums, reverse=True)[k1]
# O(nk) time, bubble sort idea, TLE
def findKthLargest2(self, nums, k):
for i in xrange(k):
for j in xrange(len(nums)i1):
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[i1] = nums[i1], nums[tmp]
return nums[len(nums)k]
# O(k+(nk)lgk) time, minheap
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+(nk)lgk) time, minheap
def findKthLargest5(self, nums, k):
return heapq.nlargest(k, nums)[k1]
# O(n) time, quick selection
def findKthLargest(self, nums, k):
# convert the kth largest to smallest
return self.findKthSmallest(nums, len(nums)+1k)
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:], kpos1)
elif k < pos+1:
return self.findKthSmallest(nums[:pos], k)
else:
return nums[pos]
# choose the rightmost 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
Python different solutions with comments (bubble sort, selection sort, heap sort and quick sort).


I don't know why the minheap takes O(k+lgk(nk)) time, someone could provide a better explanation on why O(k+lgk(nk)) time ? thanks.
Based on on this page: 'http://www.ardendertat.com/2011/05/30/myfavoriteinterviewquestion/', 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.

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 onthefly). 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.

Hi caikehe! Thanks for the solutions. One note: the
findKthLargest4
heap solution isn'tO(k+(nk)lgk)
. You are pushing all the elements into the heap, that is alreadyO(nlogn)
. I guess you mixed it with another answer of yours https://leetcode.com/discuss/61586/pythonheapquickpartitionsolutionsnlogncomplexities

I trie quick selection but it took about 3000ms. Then I changed it to pick up a random element as pivot instead of the rightmost 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]

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