最小的K个数
描述
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围：0\le k,n \le 100000≤k,n≤10000，数组中每个数的大小0 \le val \le 1000 0≤val≤1000
要求：空间复杂度 O(n)O(n) ，时间复杂度 O(nlogn)O(nlogn)
示例1
输入：
[4,5,1,6,2,7,3,8],4
返回值：
[1,2,3,4]
说明：
返回最小的4个数即可，返回[1,3,2,4]也可以
示例2
输入：
[1],0
返回值：
[]
示例3
输入：
[0,1,2,1,2],3
返回值：
[0,1,1]
思路一：优先队列
new一个优先队列PriorityQueue，队列中所有元素均不大于队列头部元素，队列size>k时进行poll。代码如下：
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> ans = new ArrayList<>();
if(k <= 0 || input == null || input.length < k) return ans;
PriorityQueue<Integer> pq = new PriorityQueue<>(11, new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2){
return o2 - o1;
}
});
for(int x : input){
pq.offer(x);
if(k < pq.size()) pq.poll();
}
while(!pq.isEmpty()){
ans.add(pq.poll());
}
return ans;
}
思路二：快速排序
该思路转自牛客网题解，侵权删除。
快速排序思想，与一般的快速排序相比，只用操作数组的一半（大于或小于情况中的一种，有判断），原来的快速排序需要对这两种情况都进行处理（无判断）。
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
// 处理不合理的情况
if (k == 0 || k > input.length) {
return res;
}
// 快速排序及分区
quickSort(input, k, 0, input.length - 1);
// 获取数组的前k个数
for (int i = 0; i < k; ++i) {
res.add(input[i]);
}
return res;
}
private void quickSort(int[] arr, int k, int l, int r) {
if(l == r || l >= arr.length) return;
int i = l, j = r;
while (i < j) {
while (i < j && arr[j] >= arr[l]) j--;
while (i < j && arr[i] <= arr[l]) i++;
swap(arr, i, j);
}
swap(arr, i, l);
// 若i大于k，则要往前找
if (i > k) quickSort(arr, k, l, i - 1);
// 若i小于k，则要往后找
if (i < k) quickSort(arr, k, i + 1, r);
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
时间复杂度：O(n)，对于长度为 n 的数组执行哨兵划分操作的时间复杂度为 O(n) ；每轮哨兵划分后根据 k 和 i 的大小关系选择递归，由于 i 分布的随机性，则向下递归子数组的平均长度为 n/2 ；因此平均情况下，哨兵划分操作一共有 n + n/2 + n/4 + … + n/n = n + (n-1)/n < 2n ，总体时间复杂度为 O(n)。
空间复杂度：O(logn)，划分函数的平均递归深度为O(logn)。