原题
在N个数组中找到第K大元素
样例
n = 2 数组 [[9,3,2,4,7],[1,2,3,4,8]], 第三大元素是 7.
n = 2 数组 [[9,3,2,4,8],[1,2,3,4,2]], 最大数是 9, 次大数是 8, 第三大数是 7
解题思路
- 维护一个大小为k的Min Heap，扫面N个数组的每一个数
- 若小于等于堆顶，跳过
- 若大于堆顶，则剔除堆顶元素，加入该元素
完整代码
import Queue
class Solution:
# @param {int[][]} arrays a list of array
# @param {int} k an integer
# @return {int} an integer, K-th largest element in N arrays
def KthInArrays(self, arrays, k):
# Write your code here
minHeap = Queue.PriorityQueue()
for nums in arrays:
for num in nums:
if minHeap.qsize() < k:
minHeap.put(num)
elif num > minHeap.queue[0]:
minHeap.get()
minHeap.put(num)
return minHeap.queue[0]
