Top K Scores

Lab Java Advanced 30 points

Read n scores and k. Keep only the k largest in a min-heap of size k as you read, then print them in descending order.

Input

n, the scores, then k.

Output

One line.

Example

Input

8
40 90 15 70 85 60 99 10
3

Output

99 90 85

Sample input available Sample output available

Editor

Java

Hints

When the heap grows past k, remove its smallest element.

Solution explanation

This keeps memory at O(k) even for huge inputs - the standard "top K" technique.

Show solution

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] scores = new int[n];
        for (int i = 0; i < n; i++) {
            scores[i] = sc.nextInt();
        }
        int k = sc.nextInt();
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        for (int s : scores) {
            heap.add(s);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        List<Integer> top = new ArrayList<Integer>(heap);
        Collections.sort(top, Collections.<Integer>reverseOrder());
        StringBuilder sb = new StringBuilder();
        for (int s : top) {
            sb.append(sb.length() > 0 ? " " : "").append(s);
        }
        System.out.println(sb);
    }
}

Output

Answer