狛 枝 凪 斗
2022-02-05 10:56
采纳率: 80%
浏览 17

随机选择算法oj题 我的代码错在哪里?

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

给定一个长度为n(1≤n≤1,000,000)的无序正整数序列,以及另一个数k(1≤k≤1,000,000),求该序列中第k小的数

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

以下为我的代码:


#include<iostream>
#include<cstdio>

using namespace std;

int Partition(int a[],int left,int right){
    int temp=a[left],i=left,j=right;
    while(i!=j){
        while(i!=j&&a[j]>temp){
            j--;
        }
        a[i]=a[j];
        while(i!=j&&a[i]<=temp){
            i++;
        }
        a[j]=a[i];
    }
    a[i]=temp;
    return i;
}

int randselect(int a[],int left,int right,int k){
    if(left==right)return a[left];
    int p=Partition(a,left,right);
    int m=p-left+1;
    if(m==k)return a[p];
    if(m>k)return randselect(a,left,p-1,k);
    if(m<k)return randselect(a,p+1,right,k-m);
}

int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    int a[1000001];
    int i,j;
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    printf("%d",randselect(a,0,n-1,k));
    return 0;
}
运行结果及报错内容

我没有输入,它自己运行几秒就自己结束了

img

1条回答 默认 最新

相关推荐 更多相似问题