Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1371
Question Name: K Least Numbers
Question Description: Given an integer array and an integer K, find the sorted K least numbers in the original array.
Input: the input might contain multiple test cases. Each test case contains two lines. The first line includes two integers N and K (1 <= K <= N <= 200000). The second line includes N integers as the input array.
Output: For each test case, print the K least numbers in increasing order.
1 2 3 4 5 | Input: 8 4 4 5 1 6 2 7 3 8 Output: 1 2 3 4 |
The solution with Java’s built-in priority queue is:
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/27/2014 * Last updated: 08/27/2014 * * Filename: KLeastNumbers.java * Compilation: javac KLeastNumbers.java * Execution: java KLeastNumbers * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Arrays; import java.util.PriorityQueue; /** * An utility to find the K least numbers in a give array. * @author Sheng Yu codesays.com */ public class KLeastNumbers { /** * Find the K least numbers in input array. Sort and return these K numbers. * @param input the original array. * @param k the count of least numbers to return. * @return the sorted K least numbers in input. */ public int[] findKLeast(int[] input, int k) { // The implementation of priority queue in Java is a min heap. // But we want a max heap. So when we push add a new item I, // we are actually add -I (negative I). PriorityQueue<Integer> kLeast = new PriorityQueue<Integer>(); // Keep the priority queue be k size at most, when adding numbers // to it. for (int item : input) { if (kLeast.size() == k) { if (-item <= kLeast.peek()) continue; else kLeast.poll(); } kLeast.add(-item); } // Store the k least numbers, and sort the result. int[] result = new int[k]; int index = 0; for (Integer i : kLeast) result[index++] = -i.intValue(); Arrays.sort(result); return result; } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int total = 0; int want = 0; int[] input = null; int[] output = null; StringBuilder sb = new StringBuilder(); KLeastNumbers findLeast = new KLeastNumbers(); while (st.nextToken() != StreamTokenizer.TT_EOF) { // Get the test case total = (int) st.nval; st.nextToken(); want = (int) st.nval; input = new int[total]; for (int i = 0; i< total; ++i) { st.nextToken(); input[i] = (int) st.nval; } // Find the K least numbers, and print them. output = findLeast.findKLeast(input, want); for (int i : output) { sb.append(i); sb.append(" "); } sb.deleteCharAt(sb.length()-1); System.out.println(sb); sb.setLength(0); } } } |