实践题目:寻找第k小的数

寻找第k小的数

设计一个平均时间为O(n)的算法，在n(1<=n<=1000)个无序的整数中找出第k小的数。
提示：函数int partition(int a[],int left,int right)的功能是根据a[left]_{a[right]中的某个元素x（如a[left])对a[left]}a[right]进行划分，划分后的x所在位置的左段全小于等于x,右段全大于等于x,同时利用x所在的位置还可以计算出x是这批数据按升非降序排列的第几个数。因此可以编制int find(int a[],int left,int right,int k)函数，通过调用partition函数获得划分点，判断划分点是否第k小，若不是，递归调用find函数继续在左段或右段查找。

输入格式:

输入有两行：
第一行是n和k，0<k<=n<=10000
第二行是n个整数

输出格式:

输出第k小的数

输入样例:
在这里给出一组输入。例如：

10 4
2 8 9 0 1 3 6 7 8 2

输出样例:
在这里给出相应的输出。例如：

2

问题描述

在无序的一堆数中找出第 k 小的数，时间复杂度要求为 O（n）

算法描述

using namespace std;
int n;

//找出 x 是第几个数
int partition(int a[],int left, int right){
    int i = left,j=right+1;
    int x=a[left];
    //将小于 x 的元素交换到左边，大于 x 的数交换到右边
    while (1){
        //如果位置是正确的就继续
        while (a[++i]<x);
        while (a[--j]>x);
        //遍历完就结束
        if (i >=j)
            break;
        //位置不对就交换
        swap(a[i],a[j]);
    }
    a[left]=a[j];
    a[j]=x;
    //返回 x 的位置
    return j;
}

//找出划分点为 x 的情况
int Find(int Array[],int left,int right,int k)
{
    //终止条件
    if(left == right)
        return Array[left];
    //用 pivot 记录划分点的位置
    int pivot = partition(Array,left,right);
    int num = pivot - left + 1;
    if(num == k)
        return Array[pivot];
    //如果第 k 小的数在划分点的右边
    else if(num < k)
        return Find(Array,pivot+1,right,k-num);
    //如果第 k 小的数在划分点的左边
    else
        return Find(Array,left,pivot-1,k);
}
int main(){
    cin >> n;
    int k;
    cin >>k;
    int a[100003];
    for (int i = 0; i < n; ++i) {
        cin >>a[i];
    }
    cout << Find(a,0,n-1,k);
    return 0;
}

算法时间及空间复杂度分析

• partition 的最坏的情况是在划分的时候出现一边 n-1 和一边为 1 的情况，最坏时间复杂度 T(n) = T(n-1)+O(n) = O（n2）
• partition 的最好情况是刚好元素大致平分，T（n）= 2T(n/2) + O(n) = O(nlogn).
• partition 的平均空间复杂度为 O(logn)。
• find 的时间复杂度为 O（logn），空间复杂度为 O(logn)。

心得体会

• 时间复杂度和空间复杂度的分析很重要但是自己还是没能掌握的很好。
• 编程的时候需要仔细认真分析题目，我们比较适合先完全分析完题目再开始编程，不然编程过程频繁出错。