剑指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 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
****************************************************************/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏带你撸出一手好代码

从PHP代码的细节说起

因为一个BUG, 我在一个摇摇欲坠,几乎碰一下就会散架的项目中某一个角落中发现下面这样一段代码 ? 这段程序与那个BUG有密切的关系。 我来回反复的捉摸这段代码...

4297
来自专栏Golang语言社区

第十节 Go语言函数方法(上)

干货来了!!!为了让更多的小伙伴喜欢Golang、加入Golang之中来,Golang语言社区发起人彬哥联合业界大牛共同推出了Go语言基础、进阶、提高课程,目前...

792
来自专栏我杨某人的青春满是悔恨

Swift API 设计指南(上)

本文翻译自苹果官方文档:Swift API Design Guidelines,如有错漏,欢迎指出。

1133
来自专栏顶级程序员

Python 工匠:善用变量来改善代码质量

我一直觉得编程某种意义上是一门『手艺』,因为优雅而高效的代码,就如同完美的手工艺品一样让人赏心悦目。

1223
来自专栏司想君

即学即用系列一:纯函数

最近一直在思考如何通过文章或者培训快速提升团队的编码能力,总结下来其实技术的学习分为两类:一种是系统性的学习,比如学习一门语言,学习一个开发框架,这更需要自己从...

2827
来自专栏C语言及其他语言

第一个 C 语言编译器是怎样编写的?

作者: 伯乐在线 - Chaobs 网址: http://blog.jobbole.com/94311/ 首先向C语言之父Dennis Ritchie致敬! ...

4259
来自专栏magicsoar

Effective Modern C++翻译(1):序言

/*********************************************************** 关于书: 书是我从网上找到的effec...

1969
来自专栏工科狗和生物喵

【计算机本科补全计划】C++牛客网试题习题解析

正文之前 一大早醒来,外面淅淅沥沥的雨绵绵的下着,床铺真的舒服,但是我也不能就在床上刷微博看小说吧,所以想起了昨晚下载的牛客网的APP,赶紧掏出我的大宝贝---...

3857
来自专栏landv

C语言介绍

4312
来自专栏Crossin的编程教室

【Python 第25课】 初探list

昨天课程里的例子有点没说清楚,有同学表示写在程序里发生了错误。因为我当时写这个代码片段时,心里假想着这是在一个函数的内部,所以用了return语句。如果你没有把...

3206

扫码关注云+社区

领取腾讯云代金券