求数组中第k个最小数

一、问题描述

给定一个数组，数组中的数据无序，在一个数组中找出其第k个最小的数，例如对于数组x，x = {3，2，1，4，5，6}，则其第2个最小的数为2。

二、解题思路

本算法跟快排的思想相似，首先在数组中选取一个数centre作为枢纽，将比centre小的数，放到centre的前面将比centre大的数，放到centre的后面。如果此时centre的位置刚好为k，则centre为第k个最小的数；如果此时centre的位置比k前，则第k个最小数一定在centre后面，递归地在其右边寻找；如果此时centre的位置比k后，则第k个最小数一定在centre后面，递归地在其左边寻找。

注意：centre的位置=其下标值+1，因为数组中的第一个元素的下标为0。

从上面的描述中，我们可以看到这个算法运用了减治的方法求解。减治的思想与分治非常相似，同样是在一次操作中，削减问题的规模，只是分治把每个子问题求解后，要合并每个子问题的解才能得到问题，而减治的方法，却不用合并子问题的解，子问题的解，直接就是原问题的解。举个例子来说，就像快排和二分查找算法，前者是分治，后者是减治。因为快排要等到所有的子数组都排完序，原数组才有序，而二分查找却不用，它每执行一次查找，直接丢弃一半的数组，而不用合并子问题的解。不过也有不少书，把他们都归为分治法。

三、代码实现

考虑到代码的通用性，使用了模板函数，如果看不懂模板函数，则只需要忽略template<typename T>，并把T看作是一个类型即可。代码如下：

[cpp] view plaincopyprint?

//返回数组中的第k个最小元素的启动函数，注意会破坏原数组  

template<typename T>  

T FindTheKMin(T *x, int x_size, int k);  

//实现查找数组中第K个最小元的功能函数  

template<typename T>  

T TheKMin(T *x, int left, int right, int k);  

template<typename T>  

T FindTheKMin(T *x, int x_size, int k)  

{  

    //判断k的值是否过大，即超过数组的大小  

    //若是则返回第0个元素，主要是为了防止无效的递归  

    if(x_size < k)  

        return x[0];  

    return TheKMin(x, 0, x_size-1, k);  

}  

template<typename T>  

T TheKMin(T *x, int left, int right, int k)  

{  

    //取数组最后一个元素为枢纽  

    T centre = x[right];  

    int i = left;  

    int j = right - 1;  

    while(true)  

    {  

        //从前向后扫描，找到第一个小于枢纽的值，  

        //在到达数组末尾前，必定结束循环,因为最后一个值为centre  

        while(x[i] < centre)  

            ++i;  

        //从后向前扫描，此时要检查下标，防止数组越界  

        while(j >= left && x[j] > centre)  

            --j;  

        //如果没有完成一趟交换，则交换  

        if(i < j)  

            Swap(x[i], x[j]);  

        else  

            break;  

    }  

    //把枢纽放在正确的位置  

    Swap(x[i], x[right]);  

    //如果此时centre的位置刚好为k，则centre为第k个最小的数  

    if(i+1 == k)  

        return x[i];  

    else if(i+1 < k)  

    {  

        //如果此时centre的位置比k前,递归地在其右边寻找  

        TheKMin(x, i+1, right, k);  

    }  

    else  

    {  

        //如果此时centre的位置比k后,递归地在其左边寻找  

        TheKMin(x, left, i-1, k);  

    }  

}  

代码说明：

在上面的代码中，我们要注意，TheKMin函数的最后的if-else，这个算法不同于快排，当枢纽不是要找到元素时，它只会选择其中一个方向的子数组继续寻找，而不像快排那样，会在两个方向的子数组中继续。从上面的代码来看，其运行速度应该在使用相同选取枢纽的策略的快排之上，时间复杂度为O(N)。

同时，当K值不合理时，我们只能返回第0个元素，这点有一点的不合理，但是，我不知道该返回一个什么样的合适的值，因为它是泛型的。

其实，这段代码有两个缺陷，第一个，就是在查找时，破坏了数组原来的数据（交换了位置）；第二个是，当类型T的复制和构造开销较大时，直接多次交换两个元素，可能会带来相当大。

另一种实现

下面，再来看看另一种实现，算法的思想和策略相同，但是使用了一个跟踪数组track，用来跟踪使用第一种方法下的数据的交换情况，利用跟踪数组的元素交换代替原数组中元素的交换，解决了上面提到的两个问题。它的实现如下：

[cpp] view plaincopyprint?

//返回数组中的第中个最小元素的下标的启动函数，不破坏原数组  

template<typename T>  

int IndexOfKMin(const T *x, int x_size, int k);  

//实现查找数组中第K个最小元下标的功能函数  

template<typename T>  

int TheKMin(const T *x, int *track, int left, int right, int k);  

template<typename T>  

int IndexOfKMin(const T *x, int x_size, int k)  

{  

    //判断k的值是否过大，即超过数组的大小  

    //若是则返回下标-1，主要是为了防止无效的递归  

    if(x_size < k)  

        return -1;  

    //创建一个跟踪数组，其内容为原数组中元素的下标，  

    //用于记录元素的交换（即代替元素的交换）  

    //按顺序以track数组中的数据为下标访问元素，访问顺序与上一方法相同  

    int *track = new int[x_size];  

    for(int i = 0; i < x_size; ++i) //初始化跟踪数组，其值与下标值相对应  

        track[i] = i;  

    int i = TheKMin(x, track, 0, x_size-1, k);  

    delete []track;  

    return i;  

}  

template<typename T>  

int TheKMin(const T *x, int *track, int left, int right, int k)  

{  

    //取数组最后一个元素为枢纽  

    T centre = x[track[right]];  

    int i = left;  

    int j = right - 1;  

    while(true)  

    {  

        //从前向后扫描，找到第一个小于枢纽的值，  

        //在到达数组末尾前，必定结束循环,因为最后一个值为centre  

        //注意此时的数据的下标不是i，而是track[i]  

        while(x[track[i]] < centre)  

            ++i;  

        //从后向前扫描时要检查下标，防止数组越界  

        while(j >= left && x[track[j]] > centre)  

            --j;  

        //如果没有完成一趟交换，则交换，注意，是交换跟踪数组的值  

        if(i < j)  

            Swap(track[i], track[j]);  

        else  

            break;  

    }  

    //把枢纽放在正确的位置  

    Swap(track[i], track[right]);  

    //如果此时centre的位置刚好为k，则centre为第k个最小的数，  

    //返回其在真实数组中的下标，即track[i]  

    if(i+1 == k)  

        return track[i];  

    else if(i+1 < k)  

    {  

        //如果此时centre的位置比k前,递归地在其右边寻找  

        TheKMin(x, track, i+1, right, k);  

    }  

    else  

    {  

        //如果此时centre的位置比k后,递归地在其左边寻找  

        TheKMin(x, track, left, i-1, k);  

    }  

}  

代码说明：

从上面的代码，我们可以看出，这个函数是返回数组中的第k个最小元的下标，所以当k不合理时，就可以返回-1来表示这个错误，同时，它使用了一个跟踪数组，track数组中的内容，实质是原数组中数据的一个索引，利用跟踪数组的元素的交换来代替了原数组元素的交换，因为该跟踪数组的数据类型是int，所以其交换速度相当快，从而解决了上面提到的两个问题。

从上面的代码，我们也可以看到，其时间复杂度与前面的实现是一样的，也为O(N)，但是，这个实现方法却带来了一定的空间开销，它开辟了一个与原数组元素个数相等的一维数组，用于跟踪原数组中的元素的交换情况。

至于在实际中，要使用哪一种算法，取决于使用者的需要！

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的求数组中第k个最小数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。