求最值问题，输入n个整数，输出其中最小的k个元素

数据结构与算法，排序 • 09 December 2014

看完两个求最大值算法之后的一些感想。 如果想直接看算法的可以跳过。但是我觉得我这些想法还是比较有用的，至少对我将来的算法设计是这样的。

算法的功能越强大，必然意味着速度慢，因为根据丛林法则，那种慢又功能少的算法会被淘汰。

所以，（注意了！！），如果我们在使用一个算法的时候感觉到它造成的结果满足我们的使用，而且超出了，我们的使用，那么我们就很可能浪费了时间，降低了效率。

例如这个1000个数中求最大的10个的算法：

如果排序，取前10个。发现后面的白排序了，根本没用到。参照加粗行，也许可以有更快的方法。 于是我们想到堆。堆之所以建立比排序快，是因为它并没有排成一队，而是多队，这个更散乱一些。也可以说，熵大一些，必然会好实现。但是我们发现，我们还是多要了条件，就是我们取出来了一个有序序列，其实并不用，这10个数的顺序我们也不要。 于是就有了（4）给出的，找到第10大的元素这样的算法。因为什么都没有浪费，所以不会再有快的了。这是肯定的。 最后还要说一点，最快的往往不是通用方法，要自己实现。

题目描述：输入n个整数，输出其中最小的k个元素。 例如：输入1，2，3，4，5，6，7，8这8个数字，则最小的4个数字为1，2，3，4。

思路1：最容易想到的方法：先对这个序列从小到大排序，然后输出前面的最小的k个数即可。如果选择快速排序法来进行排序，则时间复杂度：O（n*logn）

思路2：在思路1的基础上更进一步想想，题目并没有要求要查找的k个数，甚至后n-k个数是有序的，既然如此，咱们又何必对所有的n个数都进行排序列?如此，我们能想打的一个方法是：遍历n个数，先把最先遍历到得k个数存入大小为k的数组之中，对这k个数，利用选择或交换排序，找到k个数中的最大数kmax（kmax设为k个元素的数组中最大元素），用时O（k）（你应该知道，插入或选择排序查找操作需要O（k）的时间），后再继续遍历后n-k个数，x与kmax比较：如果x<kmax，则x代替kmax，并再次重新找出k个元素的数组中最大元素kmax‘；如果x>kmax，则不更新数组。这样，每次更新或不更新数组的所用的时间为O（k）或O（0），整趟下来，总的时间复杂度平均下来为：nO（k）=O（nk）

思路3：与思路2方法类似，只是用容量为k的最大堆取代思路2中数组的作用（从数组中找最大数需要O(k)次查找，而从更新一个堆使之成为最大堆只需要O(logk)次操作）。具体做法如下：用容量为k的最大堆存储最先遍历到的k个数，并假设它们即是最小的k个数，建堆费时O（k）后，有k1<k2<…<kmax（kmax设为大顶堆中最大元素）。继续遍历数列，每次遍历一个元素x，与堆顶元素比较，x<kmax，更新堆（用时logk），否则不更新堆。这样下来，总费时O（k+（n-k）*logk）=O（n*logk）。

思路4：按编程之美中给出的描述，类似快速排序的划分方法，N个数存储在数组S中，再从数组中随机选取一个数X（随机选取枢纽元，可做到线性期望时间O（N）的复杂度），把数组划分为Sa和Sb俩部分，Sa<=X<=Sb，如果要查找的k个元素小于Sa的元素个数，则返回Sa中较小的k个元素，否则返回Sa中所有元素+Sb中小的k-|Sa|个元素。像上述过程一样，这个运用类似快速排序的partition的快速选择SELECT算法寻找最小的k个元素，在最坏情况下亦能做到O（N）的复杂度。oh，太酷了，有没有！

思路5：仍然用到数据结构：堆。具体做法为：针对整个数组序列建最小堆，建堆所用时间为O（n），然后取堆中的前k个数，总的时间复杂度即为：O（n+k*logn）。

思路6：与上述思路5类似，不同的是在对元素数组原地建最小堆O(n)后，然后提取K次，但是每次提取时，换到顶部的元素只需要下移顶多k次就足够了，下移次数逐次减少（而上述思路5每次提取都需要logn，所以提取k次，思路7需要k*logn。而本思路只需要K^2）。此种方法的复杂度为O(n+k^2)。此方法可能不太直观，一个更直观的理解是：每次取出堆顶元素后，最小堆的性质被破坏了，我们需要调整最小堆使之满足最小堆的性质。由于我们只需要求取前k个数，我们无需将整个堆都完整的调整好，只需保证堆的最上面k个数是最小的就可以，即第一趟调整保持第0层到第k层是最小堆，第二趟调整保持第0层到第k-1层是最小堆…，依次类推。

在编码实现上述思路之前，你可能需要了解：快速排序、堆排序。

思路3的一个实现：

    #include <stdio.h>
    #include <stdio.h>
    #include <stdlib.h>
    #define PARENT(i) (i)/2
    #define LEFT(i) 2*(i)+1
    #define RIGHT(i) 2*(i+1)
     
    void swap(int *a,int *b)
    {
        *a=*a^*b;  
        *b=*a^*b;  
        *a=*a^*b;  
    }
    void max_heapify(int *arr,int index,int len)
    {
        int l=LEFT(index);
        int r=RIGHT(index);
        int largest;
        if(l<len && arr[l]>arr[index])
            largest=l;
        else
            largest=index;
        if(r<len && arr[r]>arr[largest])
            largest=r;
        if(largest != index){//将最大元素提升，并递归
            swap(&arr[largest],&arr[index]);
            max_heapify(arr,largest,len);
        }
    }
     
    void build_maxheap(int *arr,int len)
    {
        int i;
        if(arr==NULL || len<=1)
            return;
        for(i=len/2+1;i>=0;--i)
            max_heapify(arr,i,len);
    }
     
    void k_min(int *arr,int len,int k)
    {
        int i;
        build_maxheap(arr,k);
        for (i = k;i < len;i++)
        {
            if (arr[i] < arr[0])
            {
                arr[0] = arr[i];
                max_heapify(arr,0,k);
            }
        }
    }
    /*
    void heap_sort(int *arr,int len)
    {
        int i;
        if(arr==NULL || len<=1)
            return;
        build_maxheap(arr,len);
        
        for(i=len-1;i>=1;--i){
            swap(&arr[0],&arr[i]);
            max_heapify(arr,0,--len);
        }
    }
    */
     
     
    int main()
    {
        int arr[10]={91,8,6,82,15,18,7,46,29,12};
        int i;
        k_min(arr,10,4);
        for(i=0;i<10;++i)
            printf("%d ",arr[i]);
        system("pause");
    }

思路4的实现 首先给出《编程之美》上给出的伪代码：

 1 Kbig(S, k):  
 2      if(k <= 0):  
 3           return []     // 返回空数组  
 4      if(length S <= k):  
 5           return S  
 6      (Sa, Sb) = Partition(S)  
 7      return Kbig(Sa, k).Append(Kbig(Sb, k – length Sa)  
 8   
 9 Partition(S):  
10      Sa = []            // 初始化为空数组  
11      Sb = []        // 初始化为空数组  
12      Swap(s[1], S[Random()%length S])   // 随机选择一个数作为分组标准，以  
13                         // 避免特殊数据下的算法退化，也可  
14                        // 以通过对整个数据进行洗牌预处理  
15                         // 实现这个目的  
16      p = S[1]  
17      for i in [2: length S]:  
18          S[i] > p ? Sa.Append(S[i]) : Sb.Append(S[i])  
19                             // 将p加入较小的组，可以避免分组失败，也使分组  
20                            // 更均匀，提高效率  
21      length Sa < length Sb ? Sa.Append(p) : Sb.Append(p)  
22      return (Sa, Sb)

一个简化实现的如下：

    #include <stdio.h>
    #include <stdlib.h>
 
    void swap(int *a,int *b)
    {
        *a=*a^*b;  
        *b=*a^*b;  
        *a=*a^*b;  
    }
    /*
    为了简单起见，这里只是单纯的选取第一个元素作为枢纽元素。这样选取枢纽，就难避免使得算法容易退化。
    */
    int k_big(int arr[],int low,int high,int k)
    {
        int pivot  = arr[low];
        int high_tmp = high;
        int low_tmp = low;
        while(low < high){
            //从右向左查找，直到找到第一个小于枢纽元素为止
            while (low < high && arr[high] >= pivot)
            {
                --high;
            }
            arr[low] = arr[high];
            //从左向右查找，直到找到第一个大于枢纽元素为止
            while (low < high && arr[low] <= pivot)
            {
                ++low;
            }
            arr[high] = arr[low];
        }
        arr[low] = pivot;
 
        if (low == k - 1)
        {
            return arr[low];
        }else if(low > k - 1)
        {
            return k_big(arr,low_tmp,low-1,k);
        }else
        {
            return k_big(arr,low+1,high_tmp,k);
        }
    }
    int main()
    {
        int arr[10]={-91,0,6,82,15,18,7,46,-29,12};
        int i;
        k_big(arr,0,9,4);
        for(i=0;i<10;++i)
            printf("%d ",arr[i]);
        system("pause");
    }

代码出处：http://www.cricode.com/968.html

博
Loading Disqus comments...
Table of Contents