【牛客网】编程题:找到无序数组中最小的k个数(146)

发布时间:2023年12月19日

[编程题]:找到无序数组中最小的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());
	}
}

文章来源:https://blog.csdn.net/qq_42139049/article/details/135091249
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。