544. top k largest numbers

explanation

应该是没有用heapify?

  1. 先建一个初始size为k的min heap
  2. 把array里的数一个个插进去,size>k的时候,pop最小的出去
  3. 剩下一个size为k的min heap,建一个result array,一个个把结果poll出来

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class  {

* @param nums: an integer array
* @param k: An integer
* @return: the top k largest numbers in array
*/
public int[] topk(int[] nums, int k) {
// write your code here
// assume nums.size >= k
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}

// iterate the min heap
int[] result = new int[k];
for (int i = 0; i < result.length; i++) {
result[--k] = minHeap.poll();
}

return result;
}
}

time complexity

  1. time : O(nlogk)
  2. space: O(k)