difficulty: Medium tags:

  • Priority Queue
  • Heap title: Top k Largest Numbers

Top k Largest Numbers

Problem

Metadata

Description

Given an integer array, find the top k largest numbers in it.

Example

Given [3,10,1000,-99,4,100] and k = 3. Return [1000, 100, 10].

题解

简单题，使用堆即可。

Java

  1. public class Solution {
  2.     /**
  3.      * @param nums: an integer array
  4.      * @param k: An integer
  5.      * @return: the top k largest numbers in array
  6.      */
  7.     public int[] topk(int[] nums, int k) {
  8.         if (nums == null || nums.length <= 1) return nums;
  10.         PriorityQueue<Integer> pq = new PriorityQueue<Integer>(nums.length, Collections.reverseOrder());
  11.         for (int num : nums) {
  12.             pq.offer(num);
  13.         }
  15.         int[] maxK = new int[k];
  16.         for (int i = 0; i < k; i++) {
  17.             maxK[i] = pq.poll();
  18.         }
  20.         return maxK;
  21.     }
  22. }

源码分析

略

复杂度分析

略