leetcode40:TOP k,快排算法

输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

此题解法:快排、优先队列、treemap、最大数据范围…

第四十题,最简单的就是使用冒泡排序,然后直接返回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
public void quickSearch(int[] arr, int lo, int hi){
if (lo > hi) {
return;
}

int start = lo;
int end = hi + 1;
int v = arr[lo];
while (true) {
while (--end >= lo && arr[end] > v);
while (++start <= hi && arr[start] < v);
if(start >= end){
break;
}
int t = arr[end];
arr[end] = arr[start];
arr[start] = t;
}

arr[lo] = arr[end];
arr[end] = v;

quickSearch(arr, lo, end - 1);
quickSearch(arr, end + 1, hi);
}

和冒泡排序相比,冒泡时间复杂度O(n^2^),快排时间复杂度为O(nlog2n),如何用快排实现本题呢?上代码:

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
class Solution4 {

/**
* 输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。
*/
public int[] getLeastNumbers(int[] arr, int k) {
if(k == 0 || arr.length < k){
return new int[0];
}
return sort(arr, 0, arr.length - 1, k - 1);
}

public int[] sort(int[] arr, int lo, int hi, int k){
// 每快排切分1次,找到排序后下标为j的元素,如果j恰好等于k就返回j以及j左边所有的
int j = quickSort(arr, lo, hi);
if(j == k) {
return Arrays.copyOf(arr, j + 1);
}

// 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
return j > k ? sort(arr, lo, j - 1, k) : sort(arr, j + 1, hi, k);
}

public int quickSort(int[] arr, int lo, int hi){
int i = lo;
int j = hi + 1;
// 假设临界的值
int v = arr[lo];
while(true) {
while(--j >= lo && arr[j] > v);
while(++i <= hi && arr[i] < v);
if(i >= j) {
break;
}
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}

// 将临界值和j所在位置进行替换
arr[lo] = arr[j];
arr[j] = v;
return j;
}

提交后效率占比还是非常可观的:

运行效率图

至此,快排完美完成,解释都在代码内,日后自己不懂再来光顾。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×