找到无序数组中最小的k个数

[编程题]找到无序数组中最小的k个数

热度指数：2420 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整型数组arr，找到其中最小的k个数。

输入描述:

输入包含两行，第一行包含两个整数n和k，代表数组arr的长度，第二行包含n个整数，代表数组arr。

输出描述:

输出包含一行，k个整数，代表数组中最小的k个整数。

示例1

输入

5 3
3 5 1 5 2

输出

3 1 2

备注:

时间复杂度，额外空间复杂度。

算法知识视频讲解

Java

pein531

维护一个大小为k的大根堆存放小的数，遇到比堆顶小的数就把堆顶弹出，放入这个小的数

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

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());
    }
}

发表于 2021-11-09 15:06:50 回复(0)