JZ40 最小的K个数
JZ40 最小的K个数
描述
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围：0 ≤ k，n ≤ 10000，数组中每个数的大小0 ≤ val ≤10000
要求：空间复杂度 O(n)，时间复杂度 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]
解析
很容易理解的求 TOPK 小的问题，比较容易想到和实现的方式就是对输入的数组递增地进行排序，当数组有序时的前 K 个数就是最小的 K 个数。不过这种方式过于低级，时间复杂度取决于排序的时间复杂度，失去了写这道题的意义。
除了直接排序外，还可以借助快速排序的思想解决这个问题。
先复习一下快速排序，快速排序的一次排序步骤为：
- 先在要排序的数组中选取一个数作为基准数（如何选也是个问题），设置临时变量保存该基准数；
- 设置 low 和 high 两个标记指针分别在数组开头和末尾，当 low < high 时进行排序；
- 若 high 指针指向的数比基准数大，则 high 减小，直到指向的数比基准数小时停止；
- 若 low 指针指向的数比基准数小，则 low 增加，直到指向的数比基准数大时停止；
- 交换 low 和 high 指向的数，完成一次交换，此时若 low < high，重复 3、4、5 步骤；
- 当 low = high 时，循环结束，它们指向的位置就是基准数在数组中的准确位置，一次排序完成；
- 交换基准数与当前 low、high 指向的数，完成基准数归位；
- 针对基准数左右两边递归应用快速排序进行排序，直至数组有序，递归停止的标记为初始的 low > high。
快速排序的思想就是针对每个基准数，找到它在数组中的准确位置，使其左边都小于它，右边都大于它。
代码清单（快速排序）
public class Solution {
public static void QuickSort(int[] arr,int start,int end) {
if(start > end)
return;
// 左右的两个标记
int low = start, high = end;
// 基准数
int index = arr[start];
while(low < high){
// 从右边开始，寻找比基准数小的数的位置
while(low < high && arr[high] >= index)
high--;
// 再到左边，寻找比基准数大的数的位置
while(low < high && arr[low] <= index)
low++;
// 交换一大一小的两数
if(low < high){
int temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
}
// 循环结束，即 low == high，此时 arr[low] 位置就是基准数在数组中的准确位置！
// 将当前位置的数与基准数进行交换，这个位置的数一定比基准数小，或就是基准数本身
// 因为循环中 high 先移动，必定位于比基准数小的数上，或直接与初始的 low 相遇
arr[start] = arr[low];
arr[low] = index;
QuickSort(arr,start,low-1);
QuickSort(arr,high+1,end);
}
}
以上为快速排序的一种实现，基准数选择每次排序的第一个数，循环中让 high 先于 low 移动。这是因为基准数处于数组中的最小处，执行交换的前提是找到一个更小的数（即 high 停止之处），才能保证即使找不到大于基准数的数，本次交换也是合理的。相反，若基准数选择最后一个数，则要让 low 先于 high 移动。
快速排序需要从哪边开始
https://blog.csdn.net/lkp1603645756/article/details/85008715
讲了这么多其实都是在说快速排序，不过搞明白快速排序后，寻找数组中的最小的 K 个数就很简单了：只要找到位于数组中第 K 个位置的基准数，其左边就是数组中最小的 K 个数了。只要借助快速排序分区的部分就可以实现了。
代码清单
import java.util.ArrayList;
public class Solution {
// 借用快速排序分区的方法 Partition
// 基于第 K 个位置的数 N 进行分区，完成后 N 左边的数都比 N 小，右边的数都比 N 大
// 此时前 K 个数就是最小的 K 个数了（不一定有序，可以看做快速排序的中间态）
public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
ArrayList result = new ArrayList();
if(input == null || k == 0)
return result;
// 直到分区分到第 K 个位置为止
int index = Partition(input,0,input.length-1);
// 为什么是 k - 1？
while(index != k-1){
// 基准数在位置 K 的右边，对左边再进行分区
if(index > k-1)
index = Partition(input,0,index-1);
// 基准数在位置 K 的左边，对右边再进行分区
if(index < k-1)
index = Partition(input,index+1,input.length-1);
}
// 找到第 K 个位置的准确数字了，此时它左边就是比他小的 K 个数！
for(int i = 0;i < k;i++){
result.add(input[i]);
}
return result;
}
// 返回当前基准数处于的位置
public int Partition(int[] input,int low,int high){
// 取第一个数作为基准数
int temp = input[low];
while(low < high){
// 从右边开始，遇到比基准数小的就移到左边
while(low < high && input[high] >= temp)
high--;
input[low] = input[high];
// 再到左边，遇到比基准数大的就移到右边
while(low < high && input[low] <= temp)
low++;
input[high] = input[low];
}
// 循环结束，即 low == high，此时这个位置就是基准数在数组中的准确位置！
input[low] = temp;
return low;
}
}
其中的 Partition 方法是快速排序的另一种具体实现方法，在排序过程中会修改基准数的位置，之前的那种实现则不会，不过都能实现快速排序就对了。
此外，还有一个问题容易忽视：寻找的基准数只要位于 K-1 上即可而不用位于 K 上。
先说问题：数组下标从0开始，若输入数组包含8个数，是没有下标为8的位置的，此时若 K 为8且程序要寻找位于 8 上的基准数，就会产生越界访问错误。
那么如果是正常情况呢？基准数处于 K-1 的位置，它左边都是比它小的 K-1 个数（包括0），还差一个数呢？这个数就是基准数本身：基准数右边都是比它大的数，即基准数也是最小的 K 个数之一！
总结
这题真要通过，随便排个序就完成了，非常简单，但这样就没什么意思了。从快速排序开始研究，搞明白了快速排序，还顺便引出了快速排序基准数选择的问题、从哪边开始的问题；再回来看这个题，又产生了不一样的思考，虽然过程很折磨，但还好搞明白了吧。本题还有一种使用大根堆的解法，我是懒得再去研究了。