首页 > 代码库 > 剑指OFFER之最小的K个数（九度OJ1371）
剑指OFFER之最小的K个数（九度OJ1371）
题目描述：
输入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]。
- 输出：
对应每个测试案例，输出最小的k个数，并按从小到大顺序打印。
- 样例输入：
8 44 5 1 6 2 7 3 8
- 样例输出：
1 2 3 4
解题思路：
我们通过快排找到第k个数，然后比他的小的都在左边，比他大的都在右边。
void getNumber(int n,int m){ int i; int begin = 0; int end = n-1; int index = patition(begin,end); while(index != m-1){ if(index > m-1){ end = index -1; index = patition(begin,end); }else{ begin = index+1; index = patition(begin,end); } }}
在进行一次快排，将数组有序的输出。
void Qsort(int begin,int end){ if(begin >= end) return ; else{ int middle = patition(begin,end); Qsort(begin,middle-1); Qsort(middle+1,end); }}
快排的代码如下：
int patition(int begin,int end){ int index,small; small = begin-1; for(index = begin;index < end;index++){ if(gArr[index] < gArr[end]){ small++; if(small != index) swap(index,small); } } small++; swap(small,end); return small;}void swap(int i,int j){ int tmp = gArr[j]; gArr[j] = gArr[i]; gArr[i] = tmp;}
全部代码：
#include <stdio.h>#include <stdlib.h>#define MAXSIZE 200000int gArr[MAXSIZE]={0};void getNumber(int n,int m);void Qsort(int begin,int end);int patition(int begin,int end);void swap(int i,int j);int main(){ int n,m,i; while(scanf("%d %d",&n,&m)!=EOF && n>=1 && n<=200000){ for(i=0;i<n;i++) scanf("%d",&gArr[i]); getNumber(n,m); Qsort(0,m-1); for(i=0;i<m-1;i++){ printf("%d ",gArr[i]); } printf("%d\n",gArr[m-1]); } return 0;}void Qsort(int begin,int end){ if(begin >= end) return ; else{ int middle = patition(begin,end); Qsort(begin,middle-1); Qsort(middle+1,end); }}void getNumber(int n,int m){ int i; int begin = 0; int end = n-1; int index = patition(begin,end); while(index != m-1){ if(index > m-1){ end = index -1; index = patition(begin,end); }else{ begin = index+1; index = patition(begin,end); } }}int patition(int begin,int end){ int index,small; small = begin-1; for(index = begin;index < end;index++){ if(gArr[index] < gArr[end]){ small++; if(small != index) swap(index,small); } } small++; swap(small,end); return small;}void swap(int i,int j){ int tmp = gArr[j]; gArr[j] = gArr[i]; gArr[i] = tmp;}/************************************************************** Problem: 1371 User: xhalo Language: C Result: Accepted Time:950 ms Memory:1696 kb****************************************************************/
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。