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

sunzz3183 · 2020-01-31 18:45:04 · 题解

题解 P1923 【求第 k 小的数】

upd:2024/12/21 更新了排版。

题目大意

设计一个平均时间为 O(n) 的算法，在 n(1\leq n\leq 5000000) 个无序的整数中找出第 k 小的数。

题目理解

因为本题要求使用 O(n) 的时间，所以不能直接采用排序然后输出的方法来解题。因此采用分治方法，先任意找数组中的一个元素 a，采用快速排序将数组进行一次划分，即将小于 a 的元素放在其左侧，大于 a 的元素放在其右侧。然后判断元素 a 是否满足题目为第 k 小的数，满足则直接输出，否则判断下一次在哪一区间进行划分。

快排：

int quicksort(int left,int right)
{//将数组a的第left到right个元素进行划分
    int mid=a[left];
    while (left<right) 
    {//采用快排策略
        while (left<right&&mid<=a[right])
            right--;
        a[left] = a[right];
        while (left<right&&a[left]<=mid)
            left++;
        a[right] = a[left];
    }
    a[left]=mid;
    return left;
}

查找：

int find(int left, int right, int k)
{   //在数组a的第left到right中寻找第k小的数
    int tem=quicksort(left,right);
    if(k==tem)
        printf("%d",a[k]);
    else if(k-1<tem)//判断下一次划分在哪一区间进行
        find(left,tem-1,k);
    else
        find(tem+1,right,k);
    return 0;
}

由于 cin，cout 时间过长，所以我在这里用了快读。

用 scanf 和 printf 也是可以的

完整代码

#include<bits/stdc++.h>
using namespace std;
long long a[5000010];//一定要设全局变量 
inline int read(){  //快读 
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    } 
    while('0'<=ch&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    } return x*f;
}
int quicksort(int left,int right)
{
    int mid=a[left];
    while (left<right) 
    {
        while (left<right&&mid<=a[right])
            right--;
        a[left] = a[right];
        while (left<right&&a[left]<=mid)
            left++;
        a[right] = a[left];
    }
    a[left]=mid;
    return left;
}
int find(int left, int right, int k)
{   
    int tem=quicksort(left,right);
    if(k==tem)
        printf("%d",a[k]);
    else if(k-1<tem)
        find(left,tem-1,k);
    else
        find(tem+1,right,k);
    return 0;
}
int main()
{
    int n,k;
    n=read();
    k=read();
    for(int i=0;i<n;i++)
        a[i]=read();
    find(0,n-1,k);
    return 0;
}

此代码已 AC，请放心食用。