Chris_kxt 2018-03-28 08:25 采纳率: 100%
浏览 1510
已采纳

C++语言编程 急急!!! 用分治策略

设计一个平均时间为O(n)的算法,在n(1<=n<=1000)个无序的整数中找出第k小的数。

提示:函数int partition(int a[],int left,int right)的功能是根据a[left]~a[right]中的某个元素x(如a[left])对a[left]~a[right]进行划分,划分后的x所在位置的左段全小于等于x,右段全大于等于x,同时利用x所在的位置还可以计算出x是这批数据按升非降序排列的第几个数。因此可以编制int find(int a[],int left,int right,int k)函数,通过调用partition函数获得划分点,判断划分点是否第k小,若不是,递归调用find函数继续在左段或右段查找。

输入格式:
输入有两行:

第一行是n和k,0<k<=n<=10000

第二行是n个整数

输出格式:
输出第k小的数

输入样例:
在这里给出一组输入。例如:

10 4
2 8 9 0 1 3 6 7 8 2
输出样例:
在这里给出相应的输出。例如:

2

  • 写回答

2条回答 默认 最新

  • Boover 2018-03-28 11:24
    关注
     #include <stdio.h>
    
    void swap(int a[], int i, int j)
    {
        // 交换数组a中元素i与元素j的值
        int tmp;
        tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    
    int partition(int a[], int lo, int hi)
    {
        int i = lo-1, pivot = a[lo];
        swap(a, lo, hi);
        while(lo<hi)
        {
            // 循环开始的时候i指向的是小于pivot的最后的一个位置
            if(a[lo] < pivot)
            {
                i ++;
                swap(a, i, lo);
            }
            lo ++;
        }
        i ++;
        swap(a, i, hi);
        return i;
    }
    
    int find(int a[], int left, int right, int k)
    {
        int index;
        index = partition(a, left, right);
        if(index == k)
            return a[index];
        else if(index < k)
            return find(a, index+1, right, k);
        else
            return find(a, left, right-1, k);
    }
    
    int main()
    {
        int a[10000];
        int n, k, i;
        scanf("%d", &n);
        scanf("%d", &k);
        for(i=0; i<n; i++)
            scanf("%d", &a[i]);
        printf("%d\n", find(a, 0, n-1, k-1));
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 TMC2209串口模式下读取不到寄存器的值串口助手蓝色字体是发过去的消息,绿色字体是收到的消息,第二行发送读取寄存器的指令但是没有读取到寄存器的值串口助手如下图:接线如下图,如何解决?
  • ¥15 高通安卓11提取完整线刷包软件,或者优博讯dt50顺丰刷机包
  • ¥20 C,有个译码器,换了信道就跑不出原来数据
  • ¥15 MIMIC数据库安装问题
  • ¥60 基于JTag协议开发Fpga下载器上位机,哪位大🐂有偿指导?
  • ¥20 全书网Java爬取数据
  • ¥15 怎么获取红包封面的原始链接,并且获取红包封面序列号
  • ¥100 微信小程序跑脚本授权的问题
  • ¥100 房产抖音小程序苹果搜不到安卓可以付费悬赏
  • ¥15 STM32串口接收问题