80分求助 第三个数据为什么过不了

lqx1314 @ 2024-06-16 13:32:32

#include <stdio.h>
#include <stdio.h>
int a[5000005] = { 0 };
void quicksort(int* a, int left, int right, int m)
{
    if (left > right) return;
    int key = a[(left + right) / 2], i = left, j = right;
    while (i <= j)
    {
        while (key > a[i])i++;
        while (key < a[j])j--;
        if (i <= j)
        {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i++;
            j--;
        }
    }
        if ((i - 1) == m) printf("%d", key);
        else if ((i - 1) < m) quicksort(a, i, right, m);
        else if ((i - 1) > m) quicksort(a, left, j, m);

}
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    quicksort(a, 0, n - 1, m);
    return 0;

}

by wangjingxi_ @ 2024-06-16 14:24:38

int a[5000005] = {0};

int quickselect(int* a, int left, int right, int m) {
    if (left == right) return a[left];

    int pivot = a[(left + right) / 2];
    int i = left, j = right;

    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i++;
            j--;
        }
    }

    if (left <= j && k <= j) return quickselect(a, left, j, m);
    if (i <= right && k >= i) return quickselect(a, i, right, m);
    return a[k];
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    int result = quickselect(a, 0, n - 1, m);
    printf("%d\n", result);

    return 0;
}```
没什么大变化，结构是一样的，对照原代码看一下，应该差不多，本人实测AC，求关。

by lsy18653707830 @ 2024-06-30 16:55:06

sort不好吗?

#include<bits/stdc++.h>
using namespace std;
int a[5000002],k;
int main() {
    int n;
    scanf("%d%d",&n,&k);
    for(int i=0; i<n; i++) scanf("%d",&a[i]);
    sort(a,a+n);
    printf("%d",a[k]);
}