最小的K个数

题目描述思路实现

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

思路

本题关键就是对数组排序，排序算法决定本题的时间复杂度 法1 最简单的思路，利用Java自带的sort方法（快速排序），时间复杂度O(nlogn) 法2 被广泛认同的解法：使用堆排序。若使用大顶堆，时间复杂度O(logk) 求最小的k个数，就建k个大顶堆，每个堆的堆顶元素始终是最小的（若有更小的元素进来，就把当前堆顶删掉，加入新的元素作为新堆顶） 最终输出k个堆顶，即为数组中的k个最小的数

使用优先队列实现堆，默认创建的是小顶堆，为了得到大顶堆，需要使用比较器comparator接口进行反转，再用lambda表达式传入比较器是比较简洁的写法（Java自带的方法reverseOrder也可以，但用的时候想不起来）

实现

法1：快排（Java自带方法，一行实现）

import java.util.Arrays; import java.util.ArrayList; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> res=new ArrayList<>(); //最简单的思路：排序后输出前k个（Java的sort方法是快速排序） //特殊情况 if(input.length==0 || k<=0 || k>input.length) return res; Arrays.sort(input); for(int i=0;i<k;i++){ res.add(input[i]); } return res; } }

法2：堆排序，大顶堆，时间复杂度较小

import java.util.PriorityQueue; import java.util.ArrayList; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> res=new ArrayList<>(); //堆排序：大顶堆排序时间复杂度更低（用优先队列实现堆） //特殊情况 if(input.length==0 || k<=0 || k>input.length) return res; //创建大顶堆（优先队列默认创建小顶堆，所以要使用comparator接口进行反转：用lambda实现） //lambda表达式，传入一个比较器，规则是大的反而小，所以得到一个大顶堆 PriorityQueue<Integer> maxHeap=new PriorityQueue<>((a,b)->b - a); for(int i=0;i<input.length;i++){ //如果大顶堆中没有k个堆,继续加入元素，凑够k个堆 if(maxHeap.size()<k){ maxHeap.offer(input[i]); } else{ //若当前遍历的元素比堆顶小，就删掉当前堆顶，把当前元素加入变成新的堆顶 if(input[i]<maxHeap.peek()){ maxHeap.remove(); //删除当前堆顶 maxHeap.offer(input[i]); } } } //只要大顶堆里还有元素，就全取出来加到结果集合中 while(!maxHeap.isEmpty()){ res.add(maxHeap.remove()); } return res; } }