剑指OFFER之最小的K个数（九度OJ1371）
剑指OFFER之最小的K个数（九度OJ1371）
用户1154259
发布于 2018-01-17 19:29:12
发布于 2018-01-17 19:29:12
题目描述：
输入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 4
4 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 200000
int 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
****************************************************************/本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014-06-15 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录