60分超时了，求指导

Qian1239 @ 2023-02-09 15:49:05

#include <iostream>
#include<cstdio>
#include <vector>
using namespace std;
int a[5000005];

int select (int left, int right, int k){
    if(left>=right) return a[left];
    int i=left; int j=right+1;
    int pivot=a[left];
    while(true){
        do{ i=i+1;}while(a[i]<pivot);
        do{ j=j-1;}while(a[j]>pivot);
        if(i>=j) break;
        swap(a[i],a[j]);
    }
    if(j-left+1==k) return pivot;
    a[left]=a[j];
    a[j]=pivot;
    if(j-left+1<k) //j-left+1 :左区元素的个数
        return select(j+1,right,k-(j-left)-1); //在右区中找
    else
        return select(left,j-1,k);
}

int main(){
    int n,k;
    cin>>n>>k;
    k=k+1;
    for(int i=0;i<n;i++)
    cin>>a[i];

    cout<<select(0,n-1,k)<<endl;
}

by Night_sea_64 @ 2023-02-09 16:00:21

发一波乱搞！

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int a[5000010];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    random_shuffle(a+1,a+n+1);
    sort(a+1,a+n+1);
    printf("%d\n",a[k+1]);
    return 0;
}

你会发现这个代码神奇地过了！！！（逃

by Qian1239 @ 2023-02-09 16:15:00

@Netherite_sword_666 我的代码有什么改进空间呢

by too_simple @ 2023-02-09 16:18:02

@Qian1239 您能稍微解释一下代码嘛，看不懂/wul

by too_simple @ 2023-02-09 16:27:40

@Qian1239 您这行代码有啥用吗/yiw do{ i=i+1;}while(a[i]<pivot);

by Night_sea_64 @ 2023-02-09 16:36:22

@Qian1239 我是个蒟蒻，我不会正解……

by too_simple @ 2023-02-09 16:38:04

@Netherite_sword_666 焯，红名假人

by Night_sea_64 @ 2023-02-09 16:38:48

@too_simple 可以这么认为

by Qian1239 @ 2023-02-09 19:25:18

@too_simple 我用的是分治算法，前面的部分利用快排，先把第一个数当作分界数，找到它的位置，使分界数左边的数都小于它，右边的数都大于它，之后左边的和右边的按照此方式递归，判断左边有多少个数，右边有多少个数，与k的关系，在依次递归

by too_simple @ 2023-02-09 20:36:13

@Qian1239 这不对吧，首先它是无序的，不具有单调性，但如果先递归的话，是无法确定答案是在左半边还是右半边

by ninji @ 2023-02-19 20:53:08

开O2优化