无向欧拉图 2022-04-08 15:41 采纳率: 100%
浏览 239
已结题

OJ时间超限问题,代码能改进什么地方

问题遇到的现象和发生背景

题目是输出数组第k大元素,要求多组输入,第一行是k,第二行是数组,要求时间复杂度为O(n),用数据分区+递归查找加随机选取基准就可以,我明明用的是归并排序但oj老是时间超限。

问题相关代码,请勿粘贴截图

#include<stdio.h>
#include<stdlib.h>
int main(){
int n;
int a[10000];
char c;
int k;
while(scanf("%d",&k)!=EOF){
while(scanf("%d",&a[0])!=EOF){
int n=0;
while(scanf("%d",&a[++n])){
if(c=getchar()=='\n')
break;
}
int result=quickselect(a,0,n,k);
printf("%d\n",result);
}
}
return 0;
}
void swap(int a[],int i,int j){
int t=a[i];
a[i]=a[j];
a[j]=t;
}
int random(int p,int q){
return rand()%(q-p+1)+p;
}
int rpart(int a[],int p,int q){
int r=random(p,q);
swap(a,p,r);
int i=part(a,p,q);
return i;
}

int part(int a[],int p,int q){
int x=a[p];
int i=p,j;
for(j=p+1;j<=q;j++){
if(a[j]>=x){
i++;
swap(a,i,j);
}
}
swap(a,p,i);
return i;
}
int quickselect(int a[],int p,int q,int k){
if(p==q){
return a[p];
}
else{
int i=rpart(a,p,q);
int j=i-p+1;
if(k<=j){
return quickselect(a,p,i,k);
}
else{
return quickselect(a,i+1,q,k-j);
}
}

}

运行结果及报错内容
我的解答思路和尝试过的方法

想问问我这个代码需要改进什么地方

我想要达到的结果
  • 写回答

3条回答 默认 最新

  • aabyte 2022-04-08 15:50
    关注

    题目呢?另外快排时间复杂度也是O(nlogn)啊

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
  • 关注

    归并排序:

    
    #define _CRT_SECURE_NO_WARNINGS 1
    #include <stdio.h>
    #include <stdlib.h>
    
    void Merge(int R[], int low, int m, int high)
    {
        //将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high]  
        int i = low, j = m + 1, p = 0;                //置初始值  
        int* R1;                        //R1是局部向量  
        R1 = (int*)malloc((high - low + 1) * sizeof(int));
        if (!R1)
        {
            return;                         //申请空间失败  
        }
    
        while (i <= m && j <= high)                //两子文件非空时取其小者输出到R1[p]上  
        {
            R1[p++] = (R[i] <= R[j]) ? R[i++] : R[j++];
        }
    
        while (i <= m)                         //若第1个子文件非空,则复制剩余记录到R1中  
        {
            R1[p++] = R[i++];
        }
        while (j <= high)                      //若第2个子文件非空,则复制剩余记录到R1中  
        {
            R1[p++] = R[j++];
        }
    
        for (p = 0, i = low; i <= high; p++, i++)
        {
            R[i] = R1[p];                     //归并完成后将结果复制回R[low..high]  
        }
    }
    
    void MergeSort(int R[], int low, int high)
    {
        //用分治法对R[low..high]进行二路归并排序  
        int mid;
        if (low < high)
        {   //区间长度大于1   
            mid = (low + high) / 2;               //分解  
            MergeSort(R, low, mid);           //递归地对R[low..mid]排序  
            MergeSort(R, mid + 1, high);        //递归地对R[mid+1..high]排序  
            Merge(R, low, mid, high);          //组合,将两个有序区归并为一个有序区  
        }
    }
    
    int main()
    {
        int n;
        int a[10000];
        char c;
        int k;
        while (scanf("%d", &k) != EOF)
        {
            n = 0;
            while (scanf("%d", &a[n]))
            {
                n++;
                c = getchar();
                if (c == '\n')
                    break;
            }
    
            MergeSort(a, 0, n - 1);
            printf("%d\n", a[n - k]);
        }
        return 0;
    }
    
    
    
    
    评论 编辑记录
  • 有问必答小助手 2022-04-10 09:25
    关注
    您好,我是有问必答小助手,您的问题已经有小伙伴帮您解答,感谢您对有问必答的支持与关注!
    PS:问答VIP年卡 【限时加赠:IT技术图书免费领】,了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 4月18日
  • 已采纳回答 4月10日
  • 修改了问题 4月9日
  • 修改了问题 4月8日
  • 展开全部

悬赏问题

  • ¥20 反编译一款APP手游,解密出lua脚本。
  • ¥15 报错问题,只有两个错误,如图片所示,i多次初始化
  • ¥15 matlab runtime 如何收费
  • ¥20 用C语言绘制cs1.6方框透视 出现了点问题 绘制不上去 矩阵数据 和敌人坐标都是正确的
  • ¥15 Tpad api账户 api口令
  • ¥30 ppt进度条制作,vba语言
  • ¥15 生信simpleaffy包下载
  • ¥15 在二层网络中,掩码存在包含关系即可通信
  • ¥15 端口转发器解析失败不知道电脑设置了啥
  • ¥15 Latex算法流程图行号自定义