求第k小数

这篇文章包括题目、思路、代码、时间复杂度分析几部分。

题目：洛谷求第k小的数

这里的k可以取0，也就是有第0小的数（最小的数），所以，实际上相当于平常说的求第k+1小的数

想到了几种做法，

首先，排序，输出num[k]；

其次，用一个辅助数组保存前（k+1）个最小的数，遍历原数组的时候更新辅助数组（可以遍历或者大根堆），最后输出这个辅助数组中的最大值；

然后，还可以用快速排序的二分思想，将数组分成小于基准的数、基准、大于基准的数共三部分，比较k和基准的序号，相等输出基准值，小于递归基准左侧的部分，大于递归基准右侧的部分，相当于二分查找和快速排序的结合。

下面是第二种和第三种的代码

//方法二
#include <stdio.h>
#define MAXSIZE 5000000

long long num[MAXSIZE];//辅助数组，存储已遍历的前k+1小的数


int main()
{
    long long n, k,tmp;
    long long max = 0, max_node = 0, top = -1;

    scanf("%lld", &n);
    scanf("%lld", &k);
    for (long long i = 0; i < n; i++)
    {
        scanf("%lld", &tmp);
        if (top < k)//开始时，辅助数组元素个数小于k+1，直接加入
        {
            num[++top] = tmp;
            if (max < tmp)//记录好辅助数组的最大值和最大值的序号
            {
                max = tmp;
                max_node = top;
            }
        }
        else//当辅助数组加入了k+1个元素之后
        {
            if (max > tmp)//如果tmp小于辅助数组当前的最大值
            {
                max = tmp;
                num[max_node] = tmp;//将最大值元素替换为tmp
                for (long long i = 0; i <= top; i++)//遍历辅助数组，重新选取最大值和最大值结点
                    if (max < num[i])
                    {
                        max = num[i];
                        max_node = i;
                    }
            }
        }
    }
    printf("%lld", max);
    return 0;
}

//方法三
#include <stdio.h>
#define MAXSIZE 5000000

long long num[MAXSIZE];
long long n, k;

void sort(long long left, long long right)
{
    if (left > right)
        return;
    long long greater = left, less = right, std = num[left];
    while (greater < less)
    {
        while (less > greater&&num[less] >= std)
            less--;
        while (greater < less&&num[greater] <= std)
            greater++;
        if (greater != less)
        {
            long long tmp = num[less];
            num[less] = num[greater];
            num[greater] = tmp;
        }
        else
        {
            long long tmp = num[less];
            num[less] = num[left];
            num[left] = tmp;
        }
    }

    if (less == k)//原本的两部分都要递归变成了只递归一部分
        printf("%lld", num[less]);
    else if (less > k)
        sort(left, less - 1);
    else
        sort(less + 1, right);
}

int main()
{

    scanf("%lld", &n);
    scanf("%lld", &k);
    for (long long i = 0; i < n; i++)
        scanf("%lld", &num[i]);
    sort(0, n - 1);

    return 0;
}

时间复杂度分析

第一种，时间复杂度为O（n*log n），太大

第二种，时间复杂度为O（n~k*n），这种方法的最好和最坏的时间复杂度相差很大，最好的情况是原数组升序排列，时间复杂度为n，最坏的情况是原数组降序排列，时间复杂度为kn，当k≈n时，更是达到n2的级别，

第三种，时间复杂度为Θ（n），写出递推方程T(n)=T(n/2)+O(n)，利用主定理可以求解，而且最好和最坏时间复杂度都是Θ（n）

最后的结果是第一种60分，第二种0分、开 O2 40分，第三种100分（开O2更慢）

可能是测试样例太刁钻，导致第二种成绩这么差吧，唉~

第二种，如果把辅助数组当做大根堆，每次更新堆而不是遍历数组，那么时间复杂度是O（n*log k）