【牛客网】编程题：找到无序数组中最小的k个数（146）

[编程题]：找到无序数组中最小的k个数
热度指数：2394时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解
给定一个整型数组arr，找到其中最小的k个数。

输入描述:
输入包含两行，第一行包含两个整数n和k(1 \leq k \leq n \leq 10^5)(1≤k≤n≤10 5 )，代表数组arr的长度，第二行包含n个整数，代表数组arr(1 \leq arr_i \leq 10^9)(1≤arr i≤10 9)。

输出描述:
输出包含一行，k个整数，代表数组中最小的k个整数。
示例1
输入
5 3
3 5 1 5 2
输出
3 1 2

备注:
时间复杂度O(nlog_2k)和O(n)O(nlog2k)和O(n)，额外空间复杂度O(n)O(n)。

Java代码：

package com.day02;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.PriorityQueue;
import java.util.Comparator;

/*
 * 
	[编程题]：找到无序数组中最小的k个数
	热度指数：2394时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
	算法知识视频讲解
	给定一个整型数组arr，找到其中最小的k个数。
	
	输入描述:
	输入包含两行，第一行包含两个整数n和k(1 \leq k \leq n \leq 10^5)(1≤k≤n≤10 5 )，代表数组arr的长度，第二行包含n个整数，代表数组arr(1 \leq arr_i \leq 10^9)(1≤arr i≤10 9)。
	
	输出描述:
	输出包含一行，k个整数，代表数组中最小的k个整数。
	示例1
	输入
	5 3
	3 5 1 5 2
	输出
	3 1 2
	
	备注:
	时间复杂度O(nlog_2k)和O(n)O(nlog2k)和O(n)，额外空间复杂度O(n)O(n)。
	
 */

public class Main {
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]);
        String[] arr = br.readLine().split(" ");
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        for(int i = 0; i < n; i++){
            if(maxHeap.size() < k){
                maxHeap.offer(Integer.parseInt(arr[i]));
            }else{
                int cur = Integer.parseInt(arr[i]);
                if(maxHeap.peek() > cur){
                    maxHeap.poll();
                    maxHeap.offer(cur);
                }
            }
        }
        StringBuilder res = new StringBuilder();
        while(!maxHeap.isEmpty()) res.append(maxHeap.poll() + " ");
        System.out.println(res.toString().trim());
	}
}