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

• ``````# 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``````

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

• 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))`.

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

• This post is deleted!

• This post is deleted!

• 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

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

• 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]
``````

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

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

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