输入整数数组 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]
思路：我们的目标是找到递增排序后的第k个数。可以采用快排的思想，快排的partition操作会确定pivot在排序后的位置，将这个位置index与k进行比较，如果等于k，则返回[0, index]的数；如果index < k，则在右半边继续找；如果index > 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| class Solution {
private static final Random random = new Random(System.currentTimeMillis());
public int[] getLeastNumbers(int[] arr, int k) {
if (k < 1) {
return new int[0];
}
int left = 0;
int right = arr.length - 1;
while (true) {
int pivotIdx = partition(arr, left, right);
if (pivotIdx == k - 1) {
return Arrays.copyOf(arr, pivotIdx + 1);
} else if (pivotIdx < k - 1) {
left = pivotIdx + 1;
} else {
right = pivotIdx - 1;
}
}
}
private int partition(int[] arr, int left, int right) {
int randomIdx = random.nextInt(right - left + 1) + left;
swap(arr, left, randomIdx);
int pivot = arr[left];
int le = left + 1;
int ge = right;
while (true) {
while (le <= ge && arr[le] < pivot) {
le++;
}
while (le <= ge && arr[ge] > pivot) {
ge--;
}
if (le >= ge) {
break;
}
swap(arr, le, ge);
le++;
ge--;
}
swap(arr, left, ge);
return ge;
}
private void swap(int[] arr, int a, int b) {
int c = arr[a];
arr[a] = arr[b];
arr[b] = c;
}
}
|
