九度-1371-最小的K个数 | Acm之家
最常见的解法就是使用快速排序和大顶堆。
方法一使用快速排序的思想，划分的操作不用改，对递归部分稍作修改
方法二使用 大顶堆。
Read full article from 九度-1371-最小的K个数 | Acm之家
- 题目描述：
- 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
- 输入：
- 每个测试案例包括2行：第一行为2个整数n，k(1<=n，k<=200000)，表示数组的长度。
第二行包含n个整数，表示这n个数，数组中的数的范围是[0,1000 000 000]。
最常见的解法就是使用快速排序和大顶堆。
方法一使用快速排序的思想，划分的操作不用改，对递归部分稍作修改
int partition(int arr[], int s, int e){ |
05 | int x = arr[s]; |
06 | int r = e+1; |
07 | int l = s; |
08 | while(l < r){ |
09 | while(l<e && arr[++l] <= x); |
10 | while(r>s && arr[--r] > x); |
11 | if(l >= r) break; |
12 | swap(arr[r], arr[l]); |
13 | } |
14 | arr[s] = arr[r]; |
15 | arr[r] = x; |
16 | return r; |
17 | } |
18 | int k; |
19 | void minK(int arr[],int start,int end){ |
20 | if(start >= end) return; |
21 | int index = partition(arr,start,end); |
22 | if(index == k) return; |
23 | //类似二分的思想，比快速排序要少一个递归 |
24 | if(index > k) minK(arr,start,index-1); |
25 | else minK(arr,index+1,end); |
26 | } |
27 | const int M = 200001; |
28 | int n,arr[M]; |
29 | int main() |
30 | { |
31 | while(scanf("%d%d",&n, &k) != EOF){ |
32 | for(int i=0; i<n; i++){ |
33 | scanf("%d", &arr[i]); |
34 | } |
35 | --k; |
36 | minK(arr,0,n-1); |
37 | sort(arr,arr+k+1);//输出结果需要是排序的 |
38 | for(int i=0; i<k; i++) |
39 | printf("%d ",arr[i]); |
40 | printf("%d\n",arr[k]); |
41 | } |
42 | return 0; |
43 | } |
void adjustHeap(int idx){ |
06 | int l = idx*2 + 1; |
07 | int r = idx*2 + 2; |
08 | int largeIndex = idx; |
09 | //先检查边界。k即为要创建的堆的大小 |
10 | while( l<k || r<k ){ |
11 | if(l<k && a[l] > a[largeIndex]) largeIndex = l; |
12 | if(r<k && a[r] > a[largeIndex]) largeIndex = r; |
13 | if(largeIndex != idx){ |
14 | //交换 root和子节点。 |
15 | swap(a[idx], a[largeIndex]); |
16 | //交换之后继续调整子节点 |
17 | idx = largeIndex; |
18 | l = idx*2 + 1; |
19 | r = idx*2 + 2; |
20 | }else{ |
21 | break; //无需调整 |
22 | } |
23 | } |
24 | } |
25 | void buildHeap(){ |
26 | for(int i= (k-1)/2; i>=0; i--){ |
27 | adjustHeap(i); |
28 | } |
29 | } |
30 | int main(){ |
31 | while(scanf("%d%d", &n, &k) != EOF){ |
32 | for(int i = 0; i < k; i++) |
33 | scanf("%d", &a[i]); |
34 | buildHeap(); |
35 | for(int i = k; i < n; i++){ |
36 | scanf("%d", &a[i]); |
37 | if(a[0] > a[i]){ |
38 | swap(a[0],a[i]); |
39 | adjustHeap(0); |
40 | } |
41 | } |
42 | sort(a,a+k); |
43 | for(int i = 0; i<k-1; i++) |
44 | printf("%d ", a[i]); |
45 | printf("%d\n", a[k-1]); |
46 | } |
47 | } |
