弱弱求佬佬捞捞

telankesi @ 2023-04-02 21:21:18

by RP_INT_MAX @ 2023-04-02 21:33:40

@telankesi 代码发出来看看

by telankesi @ 2023-04-03 19:33:42

#include <stdio.h>;
#include <iostream>
#include <cstdio>
#include<algorithm>
#include <time.h>

using namespace std;
int a[10000000];
void fun(int& a, int& b) {
    int t = a;
    a = b;
    b = t;
}
void quicksort(int left, int right) {

    if (left >= right)return;

    int mid = rand()%(right-left+1)+left;
    int l = left, r = right;
    fun(a[mid], a[l]);
    int t = a[l];
    while (l < r) {
        while (r > l && a[r] >= t)
            r--;
        a[l] = a[r];
        while (r > l && a[l] <= t)
            l++;
        a[r] = a[l];

    }
    a[l] = t;
    quicksort(left, l-1);
    quicksort(l + 1, right);
}
int main() {
    int  n,k;
    srand((unsigned)time(NULL));
    scanf("%d %d", &n,&k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    quicksort(1, n);
    cout << a[k + 1];

    return 0;
}

by telankesi @ 2023-04-03 19:33:54

@RP_INT_MAX

by RP_INT_MAX @ 2023-04-03 20:39:43

@telankesi ……这道题你这么写不 T 飞才怪

by telankesi @ 2023-04-03 20:50:51

@RP_INT_MAX 不是随机化了吗

by RP_INT_MAX @ 2023-04-03 21:06:49

@telankesi 递归两次太慢了。你想想看，如果 k 小值在分割后区间的左半边，右半边还需要递归下去吗？

by RP_INT_MAX @ 2023-04-03 21:07:49

你的写法随机化以后是 O(n \log n) 的，被卡了。加上这个优化是 O(n)，可以通过。