544. 前K大数

描述

在一个数组中找到前K大的数

样例

给出 [3,10,1000,-99,4,100], k = 3.
返回 [1000, 100, 10]

思路

和上一道题 606. 第K大的元素 II 基本类似,只是本题需要用数组把前k大所有元素输出

代码

class Solution {
    /*
     * @param nums an integer array
     * @param k an integer
     * @return the top k largest numbers in array
     */
     public int[] topk(int[] nums, int k) {
         PriorityQueue<Integer> minheap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
             public int compare(Integer o1, Integer o2) {
                 return o1 - o2;
             }
         });

         for (int i : nums) {
             minheap.add(i);
             if (minheap.size() > k) {
                minheap.poll();
             }
         }

         int[] result = new int[k];
         // 最小堆抛出顺序是从小到大顺序,结果输出要求是从大到小顺序,
         // 所以要让result[k - 1]等于最小堆第一个抛出的数
         for (int i = 0; i < result.length; i++) {
             result[k - i - 1] = minheap.poll();
         }
         return result;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1. 关于诊断X线机准直器的作用,错误的是()。 (6.0 分) A. 显示照射野 B. 显示中心线 C. 屏蔽多...
    我们村我最帅阅读 10,798评论 0 5
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,767评论 0 33
  • 01. 颅脑CT扫描采用的听眶线是()。 (1.0 分) A. 外耳孔与外眼眦的连线 B. 外耳孔上缘与眶下缘的连...
    我们村我最帅阅读 3,372评论 0 6
  • 201. M-Q型显影液组合是()。 (2.0 分) A. 米吐尔与菲尼酮的组合 B. 对苯二酚和菲尼酮的组合 C...
    我们村我最帅阅读 3,614评论 0 4
  • 1. 下列叙述错误的是()。 (2.0 分) A. 质量管理包括QA和QC一切活动的全部过程 B. 影像质量是指对...
    我们村我最帅阅读 3,927评论 0 8