# Python min-heap and quick partition solutions (O(nlogn) and O(n) time complexities).

• ``````# k+(n-k)*log(k) time
def findKthLargest1(self, nums, k):
heap = nums[:k]
heapq.heapify(heap)  # create a min-heap whose size is k
for num in nums[k:]:
if num > heap[0]:
heapq.heapreplace(heap, num)
# or use:
# heapq.heappushpop(heap, num)
return heap[0]

# O(n) time, quicksort-Partition method
def findKthLargest(self, nums, k):
pos = self.partition(nums, 0, len(nums)-1)
if pos > len(nums) - k:
return self.findKthLargest(nums[:pos], k-(len(nums)-pos))
elif pos < len(nums) - k:
return self.findKthLargest(nums[pos+1:], k)
else:
return nums[pos]

# Lomuto partition scheme
def partition(self, nums, l, r):
pivot = nums[r]
lo = l
for i in xrange(l, r):
if nums[i] < pivot:
nums[i], nums[lo] = nums[lo], nums[i]
lo += 1
nums[lo], nums[r] = nums[r], nums[lo]
return lo``````

• Why quicksort-Partition method is O(n) time? should it be O(n2) the worst case??If it's a sorted array. and k = 1.
Btw, we can construct a heap with n_size, then the time complexity is O(n+klogn) which is better than a k_size heap at most cases.

• Actually, I think quicksort way should be O(kn) in this problem

• The quicksort-Partition solution every time we just need to sort half of the remaining list, so the time complexity should be `n+n/2+n/4+...=2n`, which is `O(n)`.

• but how could you know your pivot is the middle big one?

• Yes, if the pivot is not the middle one then the time complexity should be larger than `O(n)`, while here is the average case.

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