淄博网站排名外包,wordpress本地上传图片,dz增加网站标签,佛山网站建设找千界[编程题]#xff1a;找到无序数组中最小的k个数 热度指数#xff1a;2394时间限制#xff1a;C/C 2秒#xff0c;其他语言4秒空间限制#xff1a;C/C 256M#xff0c;其他语言512M 算法知识视频讲解 给定一个整型数组arr#xff0c;找到其中最小的k个数。
输入描述:
输…[编程题]找到无序数组中最小的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 33 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( );PriorityQueueInteger 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());}
}
