把pivot的position和 K-1对比（因为index是从0开始的），如果pivot index > K-1, 那么end = pivot -1. 如果pivot index < K-1, 那么start = pivot +1.如果一样，那就返回pivot对应的element
Time Complexity: worst case O(n^2), average case O(nlogn). Space: (1) 没有用recursion
4.Code
# -*- coding:utf-8 -*-
class Solution:
def findKth(self, a, n, K):
# write code here
# quick select idea:
# quick sort:
# 1. pick pivot and move element pivot to left to pivot, element > pivot, right ot pivot
# 2. recursion step 1 to go throught the left subarray, right subarray
# 3. if no longer partition, return
#
# quicksort:
# In partition part, check if K position in left or right subarray
# then only consider that subarray include K and recursion on this subarray
# until subarray contains one element, then that is K largest element
#
#base case: if K >n: return None, a == None, reutrn None
# Time: O(n^2) if array is almost sorted and recursion becomes list. O(nlogn) if not sorted
# SPace O（1） work in-place without recursion
#
#
if not a or n< K:
return None
return self.quickselect(a, n, 0, n-1,K)
def quickselect(self, a, n, start, end, K):
while start <= end-1:
pivot = self.partition(a, start, end)
if K-1 <pivot:
end = pivot-1
elif K-1 >pivot:
start = pivot+1
else:
return a[pivot]
return a[end]
def partition(self, a, start, end):
if start >= end:
return end
pivot_idx = end
fast_pt, stored_idx = start, start
while fast_pt < end:
if a[fast_pt] >= a[pivot_idx]:
a[fast_pt], a[stored_idx] = a[stored_idx], a[fast_pt]
stored_idx += 1
fast_pt += 1
a[pivot_idx] , a[stored_idx] = a[stored_idx], a[pivot_idx]
l_s = start
l_e = stored_idx -1
r_s = stored_idx +1
r_e = end
return stored_idx
用min-heap 找TopK largest 的方法
class Solution:
def findKth(self, a, n, K):
# method2: heap sort
# 1. build a min-heap using first K element in array
# 2. use min-heap to pop the minimum element repeatedly until
# the heap contain only K leement. Then the last element as top k largest
#
#
#
#
import heapq
if K >n and not a:
return None
heap = [a[i] for i in range(K)]
heapq.heapify(heap)
pt = K
while pt < n:
heapq.heappush(heap, a[pt])
heapq.heappop(heap)
pt += 1
# return the minimum value in the K largest values of array
# that is TopK largest
return heapq.heappop(heap)