求第K小元素(也即是求最小的K个数)

发表于 | 更新于 | 分类于 | 阅读次数： | 阅读次数：
本文字数： 3.3k | 阅读时长 ≈ 4 分钟

来源：《算法分析与设计：采用C++语言描述》


　　

基本思想：

　　求第k小元素（也即是求最小的K个元素）平均T=O(n)，最坏Tmax=O(n^2) –>与快速排序相同
　　对于求最大、最小元问题，在MaxMin.java中已经得到渐进时间复杂度为O(n)的算法，即线性时间算法。

当1<k<=n/logn时，可以使用堆排序求第k小元素：
　　首先构造一个堆，其时间为O(n)，然后依次输出前k个小元素，得到第k小元素。
　　由于没输出一个元素的时间为O(logn)，所以，求第k小元素的元素的时间为O(n+klogn)，这也是线性时间。
　　
　　然而，对于任意给定的k，当1<=k<=n时，要设计求第k小元素的线性时间算法，并不十分容易，需要做一番努力。 　　

代码：（由C++改写的Java代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class SelectTest {

    /**
     * 假定表中元素各不相同，并且随机选择主元，即在下标区间[left,right]中随机选择一个下标r，以该下标处的元素为主元。
     * 函数Partition对区间[left,right]的元素实施分划操作，经过一趟分划，主元的下标为j，
     * 区间[left,j-1]中的元素均小于主元，区间[j+1,right]中的元素均大于主元。
     * 此时，若k=j+1，则表示下标为j的元素就是第k小元素；若k<j+1,则在范围[left,j-1]中继续寻找，
     * 否则在范围[j+1,right]范围内继续寻找。
     * 
     * @param l 要查找的数组
     * @param k 查找的第k小元素
     * @param x 找到元素后就存储到x[0]中
     * @return 
     */
    public static int Select(int[] l, int k){
        if(l.length<=0 || k<=0 || k>l.length) //越界判断
            throw new RuntimeException("OutOfBounds");

        int left=0, right=l.length-1;
        //-----------------迭代分划---------------------------
        //返回伪随机的，均匀分布 int值介于0（含）和指定值（不包括）
        Random random = new Random();
        do{    //条件：left<=right
            int j = random.nextInt(right-left+1) + left; //注意：这里是-->在范围[left,right]内随机选择主元
            Swap(l, left, j); //将主元位置调换到left处（数组首端）
            j = Partition(l, left, right); //执行分划操作
            if(k==j+1)  return l[j];
            else if(k<j+1) right=j-1; //结合Partition函数，此处应为right=j-1，当K=0时不会发生下标越界
            else left=j; //结合Partition函数，此处不能为left=j+1，否则当K=l.length时会发生下标越界；
                         //而且由于是随机选择主元，left=j并不会导致右递归的主元一直都是l[j]
        }while(true);
    }

// 分划函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 分划函数
 *   将下标在[left,right]范围内的序列，以主元l[left]为中心
 *   分划成左右两个子序列，最后返回分划点j。
 * 
 */
public static int Partition(int[] l, int left, int right){
    //前置条件：left<=right
    int i=left, j=right+1; //哨兵位（防止越界）
    do{
        do i++; while(l[i]<l[left]&&i<right); //从首端向后找到>=l[left]的元素l[i]则停止；或i=right时停止
        do j--; while(l[j]>l[left]); //从末端向前找到<=l[left]的元素l[j]则停止；或当j=left时l[j]=l[left]自动停止

        if(i<j) Swap(l, i, j); //若大元素在小元素的前面则调换二者位置
    }while(i<j); //若未越界则继续查找和调换

    Swap(l, left, j); //调换l[left]和l[j]
    return j;
}
/** 调换两个元素的位置 **/
public static void Swap(int[] l, int i, int j) {
    int temp = l[i];
    l[i] = l[j];
    l[j] = temp;
}

// 测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void main(String[] args) {
    int[] l = new int[20];
    int k=17;
    //循环添加100内的随机数字到集合中
    for(int i=0; i<20; i++){
        Random random = new Random();
        int value = random.nextInt(100);
        l[i] = value;
    }
    System.out.println("原始所有元素：");
    System.out.println(Arrays.toString(l));
    int res = Select(l,k);
    System.out.println("第"+k+"小元素为："+res);
    //----------------------------
    System.out.println("分划后的所有元素：");
    System.out.println(Arrays.toString(l));
    System.out.println("最小的"+k+"个元素为：");
    for(int i=0; i<k; i++)
        System.out.print(l[i]+"\0");

// 改进

1
2
3
4
5
6
7
8
9
10
11
/**
* Select进阶版：
* 线性时间选择算法
*   下面讨论在最坏情况下具有线性时间的求第k小元素的算法。
*   经过精心挑选分划元素，可以使分划所得的两个子集合的大小相对接近，从而避免上述最坏情况的发生，
*   使得求第k小元素的最坏情况时间具有线性时间O(n)。
*   
*   略...（算法设计与分析P84）
*/
    }
}

---------------- The End ----------------
0%