我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷题源码[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 面试题40. 最小的k个数
题目
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
限制：
- 0 <= k <= arr.length <= 10000
- 0 <= arr[i] <= 10000
解题思路
思路1-每次取一个数放到结果数组中进行二分查找插入确定位置，时间复杂度：Nlogk（N=arr.length）
- 逐个取数放入结果数组，数组未满时进行查找位置并插入数据；
- 已放入k个数时，后续将只放比最大值还小的数，跳过大于的值；
由于进行了N次的logk查找和移动，总时间复杂度为Nlogk,其实就是TopK的思想
思路2-考虑快排，但是只需要确定前k个数是较小数无需严格有序
局部条件快排
- 先进行一次正常快排，结束位置索引为index；
- 若index大于k，说明左半边的数是较小数且数量大于k，只需对左半边进行递归快排；
- 若index小于k，说明左半边是较小数且数量小于k，此时只需对右半边进行递归快排；
虽然是局部条件快排，但平均时间复杂度应该还是NlogN（N=arr.lrngth）
But! LeetCode官方给出的是O(n):
时间复杂度：期望为 O(n) ，由于证明过程很繁琐，所以不再这里展开讲。具体证明可以参考《算法导论》第 9 章第 2 小节。
最坏情况下的时间复杂度为 O(n*n)。情况最差时，每次的划分点都是最大值或最小值，一共需要划分 n - 1次，而一次划分需要线性的时间复杂度，所以最坏情况下时间复杂度为 O(n*n)。
空间复杂度：期望为 O(logn)，递归调用的期望深度为 O(logn)，每层需要的空间为 O(1)，只有常数个变量。
最坏情况下的空间复杂度为 O(n)。最坏情况下需要划分 n 次，即 randomized_selected 函数递归调用最深 n - 1 层，而每层由于需要 O(1) 的空间，所以一共需要 O(n) 的空间复杂度。
总结：直接快排和TopK应该是比较容易想到的，但是对快排进行局部条件处理需要多思考
算法源码示例
package leetcode;
import java.util.Arrays;
/**
* @author ZhouJie
* @date 2020年3月20日 下午5:21:10
* @Description: 面试题40. 最小的k个数
*
*/
public class LeetCode_Offer_40 {
}
class Solution_Offer_40 {
/**
* @author: ZhouJie
* @date: 2020年3月20日 下午4:31:31
* @param: @param arr
* @param: @param k
* @param: @return
* @return: int[]
* @Description: 1-每次都取一个数跟已取得的数进行比较并二分查找插入，效率比较低..
* 时间复杂度：Nlogk，N=arr.length
*
*/
public int[] getLeastNumbers_1(int[] arr, int k) {
int len = 0;
if (arr == null || (len = arr.length) == 0) {
return new int[len];
}
if (k == 0) {
return new int[k];
}
if (k >= len) {
return arr;
}
int[] rst = new int[k];
int count = 0;
rst[0] = arr[0];
for (int i = 1; i < len; i++) {
if (arr[i] >= rst[count] && count < k - 1) {
rst[++count] = arr[i];
} else if (arr[i] < rst[count]) {
int low = 0, high = count;
while (low < high) {
int mid = (high + low) / 2;
if (rst[mid] < arr[i]) {
low = mid + 1;
} else {
high = mid;
}
}
int last = count;
if (count < k - 1) {
last++;
count++;
}
while (last > low) {
rst[last--] = rst[last];
}
rst[last] = arr[i];
}
}
return rst;
}
/**
* @author: ZhouJie
* @date: 2020年3月20日 下午4:40:29
* @param: @param arr
* @param: @param k
* @param: @return
* @return: int[]
* @Description: 2-条件局部快排；时间复杂度：logN N=arr.length
*
*/
public int[] getLeastNumbers_2(int[] arr, int k) {
int len = 0;
if (arr == null || (len = arr.length) == 0) {
return new int[len];
}
if (k == 0) {
return new int[k];
}
if (k >= len) {
return arr;
}
quickSort(arr, 0, len - 1, k);
return Arrays.copyOf(arr, k);
}
/**
* @author: ZhouJie
* @date: 2020年3月20日 下午4:34:58
* @param: @param arr
* @param: @param i
* @param: @param len
* @param: @param k
* @return: void
* @Description: 快排
*
*/
private void quickSort(int[] arr, int start, int end, int k) {
if (start >= end) {
return;
}
int left = start, right = end;
int midVal = arr[(left + right) / 2];
while (left <= right) {
while (left <= right && arr[left] < midVal) {
left++;
}
while (left <= right && arr[right] > midVal) {
right--;
}
if (left <= right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
// 此时left==right，数组已经分为两部分了，左边都是小于midVal的值，右边都是大于midVal的值
// 若right不小于k，说明右边的数都太大，只需要对左半边的区间[start，right]排序就可以了
// 若right小于k，说明已经找到了right个数，只需要再对区间[right，end]排序并再找到k-right个次小数就可以了，但是k的索引不需要变化
if (right >= k) {
quickSort(arr, start, right, k);
} else {
quickSort(arr, left, end, k);
}
}
}