Find the K-Largest
1. Link
2. 描述
有一个整数数组,请你根据快速排序的思路,找出数组中第 大的数。给定一个整数数组
,同时给定它的大小n和要找的
,请返回第
大的数(包括重复的元素,不用去重),保证答案存在。要求时间复杂度
示例1
输入:
[1,3,5,2,2],5,3
复制返回值:
2
复制
示例2
输入:
[10,10,9,9,8,7,5,6,4,3,4,2],12,3
复制返回值:
9
复制说明:
去重后的第3大是8,但本题要求包含重复的元素,不用去重,所以输出9
3. 思路
method 1: heapsort
use a min heap to store K elements
continue appending elements to heap and then pop the minimum one and keep the largest K elements
when we store the last K elements in heap, just pop the minimum one and return then it is the top K largest element
Note: we need to first append next element into heap to have k+1 element , then pop the smallest one. Otherwise, it is possible that we pop the K^th largest element from heap, but insert the next element smaller than the top K^th largest element to heap. This is wrong, as we miss the K^th largest element
method 2: quick select
randomly pick pivot
partition array by pivot and then return pivot position
compare pivot position with K
if pos >k: search left space of pivot recursively
if pos < k: search right space of pivot recursively
otherwise: return pos and a[pos]
4. Coding
method 1: Heap Sort
class Solution:
def findKth(self, a, n, K):
#
# method 1. heap sort
# 1. use a min heap to store K elements
# continue appending elements to heap and pop the minimum element
# and keep the largst k-1 element
# 2. when we append the last elemnt in list to the heap, then the minimum elment in heap
# is hte top K largest element in list
# 3. base case: when list has length < K, return None, doesn't exist top K largest element
# Time: O(n+k + (n-k)log(k))
import heapq
if not a or n< K :
return None
i = 0
heap = []
# time : O(k)
while i < K:
heap.append(a[i])
i += 1
# time: O(n)
heapq.heapify(heap)
# time: O((n-k)log(k) )
res = None
# Note: here we need to push the next element before poping the smallest one
# since we want to keep the largest K elements
# if we first pop then push, it is possible that we pop the K largest element and
# then push the smaller one into heap, so that we miss the the K largest
while i < n:
heapq.heappush(heap, a[i])
heapq.heappop(heap)
i += 1
return heapq.heappop(heap)
method 2: QuickSelect, based on Quick Sort
Last updated
Was this helpful?