原题
在一个数组中找到前K大的数
样例
给出 [3,10,1000,-99,4,100], k = 3.
返回 [1000, 100, 10]
解题思路
方法一：快速排序，然后取出前k大的数。时间复杂度O(n*logn + k)
方法二：维护一个大小为k的最大堆/最小堆，代码如下。时间复杂度为O(n * logk)
关于Heap
在python中有两个接口：heapq和Queue.PriorityQueue。其中PriorityQueue module is using the heapq module which is slower because it adds locks, encapsulation, and a nice object oriented API.
-
heapq的使用：
- heapq.heappush: Push the value item onto the heap, maintaining the heap invariant.
- heapq.heappop: Pop and return the smallest item from the heap, maintaining the heap invariant.
- heapq.heapify: Transform list x into a heap, in-place, in linear time.
-
Queue.PriorityQueue的使用 (myqueue = Queue.PriorityQueue)
- myqueue.put()
- myqueue.get()
- myqueue.qsize()
- myqueue.empty()
完整代码
import Queue
class Solution:
'''
@param {int[]} nums an integer array
@param {int} k an integer
@return {int[]} the top k largest numbers in array
'''
def topk(self, nums, k):
# Write your code here
res = []
if not nums or k == 0:
return res
MaxHeap = Queue.PriorityQueue()
for num in nums:
MaxHeap.put(-num)
for i in range(k):
res.append(-MaxHeap.get())
return res
