剑指offer第二九题。

题目描述

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

解题思路

对于这种不变的数组,第一种思路是快速排序,然后找出前几个数即可,这种方法的时间复杂度为nlogn。

第二种更优的思路是堆排,因为找到前k个数字的时间复杂度为nlogk

我的答案

快速排序:

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
53
54
55
56
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if(k > input.length || k == 0){
return res;
}

//快排
quick_sort(input,0,input.length-1);

for(int i=0;i<k;i++){
res.add(input[i]);
}

return res;
}

//只要low<high就满足递归条件
private void quick_sort(int[] arr,int low,int high){
if(low < high){
//三色国旗,每次partion之后实现将小于基准数和大于基准数的值想办法搞到两边去
//返回的数组是一个长度为2的数组,分别放等于基准数的起始坐标和终止坐标
int[] p = partion(arr,low,high);
//对小于基准数的地方再次递归来搞成三色国旗
quick_sort(arr,low,p[0]-1);
//对大于基准数的地方也再次递归搞成三色国旗
quick_sort(arr,p[1]+1,high);
}
}

//三色国旗,尤其注意的是下标
private int[] partion(int[] arr,int low,int high){
int less = low - 1;
int more = high + 1;
int curr = low;
int num = arr[curr];
while(curr < more){
//小于基准值则跟++less交换,大于基准值则跟--more交换,相等则不管,继续前进
if(arr[curr] < num){
swap(arr,++less,curr++);
}else if(arr[curr] > num){
swap(arr,curr,--more);
}else{
curr++;
}
}
return new int[]{less,more};
}

private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}

原生堆排来实现:

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> res = new ArrayList<>();

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
//由于是找前k个数字,是比较小的,所以适合用小跟堆来解决
//因为大根堆先得到的是最大值,时间复杂度无法达到理想的nO(k)
//整个过程是对数组进行操作的,但是与操作一颗二叉树是一样的,因为二叉堆是可以用数组来表示的
//数组的第一个元素就是二叉堆的root
//我们要保证是最小堆,那么每次从root拿到的数必然是最小的数
//root提取出来之后,将root和最后一个数交换后需要重新调整堆维持堆的性质

if(k == 0 || k > input.length){
return res;
}

heapSort(input,k);

return res;
}

private void heapSort(int[] arr,int k){
if(arr == null || arr.length < 2){
return;
}

//初步构建起一个最小堆,此时root是最小的一个数
for(int i=0;i<arr.length;i++){
heapInsert(arr,i);
}

int heapSize = arr.length;
swap(arr,0,--heapSize);
//将最小的数此时也放进list中,如果k恰好为1那么直接返回
res.add(arr[heapSize]);
if(res.size() == k){
return;
}

while(heapSize > 0){
//在对[0,heapSize]间构建最小堆,每一轮都找到最小值,然后交换到最后
heapify(arr,0,heapSize);
swap(arr,0,--heapSize);
//每次都将堆中最小的数拿到heapSize索引处,所以直接添加进结果集中,结果集大小为k了则立即结束
res.add(arr[heapSize]);
if(res.size() == k){
return;
}
}
}

//初步构建最小堆,即构建完毕之后root为堆中最小值
private void heapInsert(int[] arr,int i){
while(arr[i] < arr[(i-1)/2]){
//如果比它的父亲小则与父亲交换
swap(arr,i,(i-1)/2);
i = (i-1)/2;
}
}


//上浮过程,每次将root和最后一个数字进行交换,然后重新构建最小堆
private void heapify(int[] arr,int index,int heapSize){
int left = index * 2 + 1;
while(left < heapSize){
//如果右子节点也没有越界的话,则从左右中挑出一个最小值
int largest = left+1 < heapSize && arr[left+1]<arr[left] ? left+1 : left;
//再与当前结点做比较
int maxIndex = arr[index] < largest ? index : largest;
//最小的就是index的话,则不用再比较了,已经是最小值了
if(maxIndex == index){
break;
}
//不是的话,则要进行交换
swap(arr,index,largest);
index = maxIndex;
left = index * 2 + 1;
}
}

private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}