题目：
题解：
1、快速排序
解题思路：对原数组从小到大排序后取出前 k 个数即可。
复杂度分析：
- 时间复杂度 O(NlogN) ： 库函数、快排等排序算法的平均时间复杂度为 O(NlogN) 。
- 空间复杂度 O(N) ： 快速排序的递归深度最好（平均）为 O(logN) ，最差情况（即输入数组完全倒序）为 O(N)。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25// 快速排序
class Solution2 {
public int[] getLeastNumbers(int[] arr, int k) {
quickSort(arr, 0, arr.length - 1);
return Arrays.copyOf(arr, k);
}
private void quickSort(int[] arr, int l, int r) {
if (l >= r) 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);
quickSort(arr,l,i-1);
quickSort(arr,i+1,r);
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
2、基于快速排序的数组划分
解题思路：题目只要求返回最小的 k 个数，对这 k 个数的顺序并没有要求。因此，只需要将数组划分为 最小的 k 个数 和 其他数字 两部分即可，而快速排序的哨兵划分可完成此目标。
复杂度分析：
本方法优化时间复杂度的本质是通过判断舍去了不必要的递归（哨兵划分）。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27// 快速排序优化版
class Solution3 {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
if (k >= arr.length) return arr;
return quickSort(arr, k-1, 0, arr.length - 1);
}
private int[] quickSort(int[] arr, int k, int l, int r) {
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);
if (i > k) return quickSort(arr, k, l, i - 1);
if (i < k) return quickSort(arr, k, i + 1, r);
return Arrays.copyOf(arr, k+1);
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}