大佬们,是我题意没有理解清楚吗,最小的数是第0小,为啥提交完一个都不对呢

P1923 【深基9.例4】求第 k 小的数

_Hal @ 2023-07-21 12:18:09

#include <iostream>
#include <string>

const int N = 50000010;
int k;
int arr[N];
void swap(int& a, int&b)
{
    int temp = a;
    a = b;
    b = temp;
}
int qu_sort(int arr[], int l, int r, int k)
{
    if (l == r)
    {
        return arr[l];
    }
    int i = l - 1, j = r + 1, x = arr[l + r >> 1];
    while (i < j)
    {
        do
        {
            i++;
        } while (arr[i] < x);
        do
        {
            j--;
        } while (arr[j] > x);
        if (i < j)
        {
            swap(arr[i], arr[j]);
        }
    }
    int len = r - l + 1;
    if (k < len)
    {
        qu_sort(arr, l, j, k);
    }
    else
    {
        qu_sort(arr, j + 1, r, k - len);
    }
}
int main()
{
    int i, n;
    scanf("%d %d\n", &n, &k);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    std::cout << qu_sort(arr, 0, n - 1, k + 1);

    system("pause");

    return 0;
}

by __Tonycyt__ @ 2023-07-21 12:30:00

@ln2____ system("pause") 你想干嘛


by _Hal @ 2023-07-21 12:40:55

@Tonycyt 啊。。。不是cpp代码都有这个吗我记得。。。删掉也过不了哇。。


by __Tonycyt__ @ 2023-07-21 12:59:56

@ln2____ 我觉得就是有点没必要,你用的是快排,全红吗?


by Terrible @ 2023-07-21 13:01:44

@ln2____

int len = r - l + 1; 里面改成 j-l+1

②后面两个 qu_sort 加上 returnreturn qu_sort(arr, l, j, k);return qu_sort(arr, j + 1, r, k - len);

别刷小聪明,这个能在 G++ 不开优化的时候输出正确结果。但是你这是违法行为,走跟我去自首。用 Clang++ 编译或者在开 O2 的环境里铁定寄。


by Terrible @ 2023-07-21 13:03:53

if (k <= len) 加个等号。


by __Tonycyt__ @ 2023-07-21 13:04:19

最小的数是第0小你为啥qu_sort(arr,0,n-1,k+1)我很疑惑


by __Tonycyt__ @ 2023-07-21 13:06:06

还有你好像少了return


by Terrible @ 2023-07-21 13:06:11

@Tonycyt 细细读题。

输出这些数字的第 k 小的数。最小的数是第 0 小.

0 开始的标记转成 1 开始的标记。


by _Hal @ 2023-07-21 13:06:12

@Tonycyt 我用的是快速选择排序,O(n)的那个。。


by _Hal @ 2023-07-21 13:07:01

@Terrible 谢兄弟谢谢啦!我去看看


| 下一页