difficulty: Medium tags:

  • Priority Queue
  • Heap
  • Data Stream title: Top k Largest Numbers II

Top k Largest Numbers II

Problem

Metadata

Description

Implement a data structure, provide two interfaces:

  1. add(number). Add a new number in the data structure.
  2. topk(). Return the top k largest numbers in this data structure. k is given when we create the data structure.

Example

  1. s = new Solution(3);
  2. >> create a new data structure.
  3. s.add(3)
  4. s.add(10)
  5. s.topk()
  6. >> return [10, 3]
  7. s.add(1000)
  8. s.add(-99)
  9. s.topk()
  10. >> return [1000, 10, 3]
  11. s.add(4)
  12. s.topk()
  13. >> return [1000, 10, 4]
  14. s.add(100)
  15. s.topk()
  16. >> return [1000, 100, 10]

题解

此题只用堆的话在最后的排序输出会比较难受，最后用 List 的排序也可以。

Java

  1. public class Solution {
  2.     private int k = -1;
  3.     private Queue<Integer> heap = null;
  4.     /*
  5.     * @param k: An integer
  6.     */public Solution(int k) {
  7.         // do intialization if necessary
  8.         this.k = k;
  9.         heap = new PriorityQueue<Integer>(k);
  10.     }
  12.     /*
  13.      * @param num: Number to be added
  14.      * @return: nothing
  15.      */
  16.     public void add(int num) {
  17.         // write your code here
  18.         if (heap.size() < k) {
  19.             heap.offer(num);
  20.         } else if (heap.peek() < num) {
  21.             heap.poll();
  22.             heap.offer(num);
  23.         }
  24.     }
  26.     /*
  27.      * @return: Top k element
  28.      */
  29.     public List<Integer> topk() {
  30.         // write your code here
  31.         List<Integer> result = new ArrayList<>(k);
  32.         Iterator<Integer> it = heap.iterator();
  33.         while(it.hasNext()) {
  34.             result.add(it.next());
  35.         }
  36.         result.sort(Collections.reverseOrder());
  37.         return result;
  38.     }
  39. }

源码分析

略

复杂度分析

略