算法分析与设计(work6)

1.问题

L是n个无序元素的集合，从L中选取第k小的元素。

2.解析

可以通过分治策略来解决。
1、以 (L) 中的某个元素 (pos) 作为基准元素，将 (L) 划分为两个集合 (L1，L2) ，其中 (L1) 中的元素都比 (pos) 小或等于 (pos) ， (L2) 中的元素都比 (pos) 大。

2、若 (k=size(L1)+1) ，那么 (pos) 就是第k小的元素，直接返回答案即可。

3、若 (k<size(L1)+1) ，那么则说明第k小元素在L1中，那么问题规模就转化为了在L1中找第k小的元素。

4、若 (k>size(L1)+1) ，那么则说明第k小元素在L2中，L2的最小元素对于L是第 $size(L1)+2 $小的元素，那么问题就转化为了在L2中找第 (（k-(size(L1)+1)）) 小的元素。

3.设计

伪代码：

int find(int L[],int k,int size)
{
    int pos=L[(size+1)/2];
    int L1[size/2+5],L2[size/2+5];
    int size1=0,size2=0;
    for(int i=1;i<=size;i++)
    {
        if(i!=(size+1)/2){
            if(L[i]<=pos)L1[++size1]=L[i];
            else L2[++size2]=L[i];
        }
    }
    if(k==size1+1){
        return pos; 
    }else if(k<size1+1){
        return find(L1,k,size1); 
    }else{
        return find(L2,k-(size1+1),size2);
    }
}

4.分析

时间复杂度：O(n)。

5.源码

github源码地址：https://github.com/HaHe-a/Algorithm-analysis-and-design-code/blob/master/k-th number.cpp