[编程之美] 2.5 寻找最大的K个数 - c++编程基础

这节给的题目是从一串数字中寻找最大的K个数，而且考虑数据量比较大的情况。

解法一首先考虑了快速排序和堆排序，但是，它们对所有的数据都进行了排序，然后考虑使用部分排序算法，如选择排序和交换排序，它们能够从一串数字中选择前K个，但是，效率依旧不高。

解法二使用了快速排序算法，在快速排序算法中，用一个枢轴将数列分成了两个部分，左边的比枢轴小，右边的比枢轴大，然后再分别对两个数列进行递归，在这里，用枢轴来分的时候，左边的比枢轴大，右边的比枢轴小，当枢轴左边的元素个数大于或者等于K，那么，就返回左边数列的最大的K个数，当枢轴左边的元素个数n小于K，就返回左边数列和右边数列的最大的n-k-1个数。书中在实现的时候用到了两个数组，这里，我就按照快速排序的过程实现一遍。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; vector
       
        ::iterator find_k(vector
        
         ::iterator beg, vector
         
          ::iterator end, int k) { vector
          
           ::difference_type n = k; if(end - beg <= n) { return end; } vector
           
            ::iterator left = beg, right = end - 1; srand(time(NULL)); int index = rand() % n; iter_swap(beg, beg + index); while(left < right) { while(*right < *left && left < right) --right; if(left < right) { iter_swap(left, right); } while(*left > *right && left < right) ++left; if(left < right) { iter_swap(left, right); } } n = left - beg; if(n + 1 >= k) return find_k(beg, left + 1, k); else return find_k(left + 1, end, k - n - 1); } int main() { int arr[] = {5, 3, 8, 1, 2, 7, 6, 9}; vector
            
              ivec(arr, arr + 8); int k = 5; vector
             
              ::iterator iter = find_k(ivec.begin(), ivec.end(), k); copy(ivec.begin(), iter, ostream_iterator
              
               (cout, " ")); return 0; }

上述的代码跟快速排序很像吧？为了使枢轴随机，不一定是第一个元素，代码使用了随机数生成函数，将第一个元素与后面的某一个元素进行调换。代码执行结果：

vce2yL+0o6y9q9X7yv2007jfzru1vbXNzrvEs867zqowu/LV3zG9+NDQtv631qGjPC9wPgo8cD694reoy8TW0KOsytfPyMzhs/bBy9K7uPbOyszio6zJz8PmtcS3vbeotrzQ6NKqttTK/b7dt8POyrbgtM6jrMjnufvK/b7dwb+63LTztcTH6b/2z8KjrMr9vt3O3reoyKu2vNewyOu1vcTatObW0KOsu+G21NCnwsrU7LPJuty087XE07DP7KGjPC9wPgo8cD7T2srHo6y+zdKqx/O+ob/JxNzJ2bXYsenA+sv509DK/b7doaM8L3A+CjxwPsrXz8ijrLzZyejK/b7dtcTHsEu49sr9vt2+zcrH1+6087XES7j2yv2+3aOsyOe5+7XaSyYjNDM7Mbj2yv2+3bHIx7BLuPbK/b7dtcTX7tChJiMyMDU0MDvQoaOsxMfDtMewSyYjNDM7Mbj21KrL2LXE1+6087XES7j21KrL2L7NysfHsEu49tSqy9ijrMjnufu12ksmIzQzOzG49sr9vt2xyMewS7j2yv2+3bXE1+7QoSYjMjA1NDA7tPOjrMTHw7SjrMewSyYjNDM7Mbj21KrL2LXE1+6087XES7j21KrL2L7Nyse9q8ewS7j21KrL2NbQ1+7QobXE1KrL2Mzes/219L7NysfBy6Gj1eLR+dbYuLSy2df3o6yx6cD6zerL+dPQtcTUqsvYuvOjrNfutPO1xEu49sr9vt3Ssr7Ns/bAtMHLo6y2+MfS1rux6cD6wcvSu7Hpyv2+3aGjsLTV1cnPyva3vbC4o6y/ydLUtcO1vdLUz8K0+sLro7o8L3A+CjxwPjwvcD4KPHByZSBjbGFzcz0="brush:java;">#include #include #include using namespace std; vector ::iterator min_iter(vector ::iterator beg, vector ::iterator end) { vector ::iterator m = beg; ++beg; while(beg != end) { if(*beg < *m) { m = beg; } ++beg; } return m; } void find_k(vector ::iterator beg, vector ::iterator end, int k) { vector ::difference_type n = k; if(end - beg <= n) { return; } vector ::iterator iter = beg + k; while(iter != end) { vector ::iterator m = min_iter(beg, beg + k); if(*iter > *m) { iter_swap(iter, m); } ++iter; } } int main() { int arr[] = {5, 3, 8, 1, 2, 7, 6, 9}; vector ivec(arr, arr + 8); int k = 5; find_k(ivec.begin(), ivec.end(), k); if(ivec.size() < k) { copy(ivec.begin(), ivec.end(), ostream_iterator (cout, " ")); } else { copy(ivec.begin(), ivec.begin() + k, ostream_iterator (cout, " ")); } return 0; }
思路上面已经解释了，代码就不做过多解释。

以上代码只需要遍历一次所有的元素，主要的瓶颈就在于min_iter()求前K个元素的最小值上，那么，能够快速地得到前K个元素的最小值吗？

可以，使用堆，对前K个元素建小顶堆，那么就能够快速得到前K个元素的最小值了。这里只给出核心函数：

void find_k(vector
  
   ::iterator beg, vector
   
    ::iterator end, int k) { vector
    
     ::difference_type n = k; if(end - beg <= n) { return; } make_heap(beg, beg + n, greater
     
      ()); vector
      
       ::iterator iter = beg + n; while(iter != end) { if(*iter > *beg) { pop_heap(beg, beg + n, greater
       
        ()); iter_swap(iter, beg + n - 1); push_heap(beg, beg + n, greater
        
         ()); } ++iter; } }

解法五首先提出了一种使用计数的方式，对每个值出现的次数进行计数，然后再从高到低得到最大的K个数，但是，这种方法仅适用于元素时正整数且取值范围不大的数据。

扩展问题：

1 如果需要找出N个数中最大的K个不同的浮点数呢？注意这里的“不同”两个字。

当然，最简单的办法就是对N个数进

[编程之美] 2.5 寻找最大的K个数(一)