大佬们,是我题意没有理解清楚吗,最小的数是第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 13:11:42

蒟蒻谢罪


by Terrible @ 2023-07-21 13:12:35

@ln2____ 具体地说,是依赖于数据随机的期望 \Theta(n) 算法,存在稳定的 hack 数据使得它退化到 \Theta(n^2),为了防止被有目的地 hack 掉,可以将数据预先随机化排列。

推荐使用 std::nth_element 函数,对任何正确的输入参数都能以 \Theta(n) 的时间复杂度计算,非常稳定。


by Terrible @ 2023-07-21 13:13:20

@Tonycyt 快去好好学习。


by _Hal @ 2023-07-21 13:20:27

@Terrible 谢谢兄弟!爱死了爱死了!!


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

@Terrible 大佬为什么要变成<=呢


by Terrible @ 2023-07-21 13:28:37

@ln2____ 你的代码将序列分成了两部分,一部分是 [l,j],这些数小于等于 x;另一部分是 [j+1,r],这些数大于等于 x,如果所求 k 是小于等于左边元素个数的话,就在左边,不是的话才在右边。

反过来想,如果 k==len 放到右边的部分,会把 k 处理成 k-len==0,这是不合乎你的函数参数的含义的。


by _Hal @ 2023-07-21 13:30:36

@Terrible 嗷嗷我缕一缕


by __Tonycyt__ @ 2023-07-21 14:30:52

@Terrible 请尽量不要使用 nth_element 来写本题,因为本题的重点在于练习分治算法。


by __Tonycyt__ @ 2023-07-21 14:31:51

我会 nth_element 要是没有这句话我早让他用了


上一页 |