题意

题目描述

输入n个整数，找出其中最小的K个数。

例如输入4,5,1,6,2,7,3,8这8个数字，
则最小的4个数字是1,2,3,4,。

分析

方法一–排序

要求一个序列中最小的K个数，按照惯有的思维方式，很简单，先对这个序列从小到大排序，然后输出前面的最小的K个数即可；

至于选取什么样的排序方法，第一时间应该想到的是快速排序，我们知道，快速排序平均时间复杂度为O(nlogn)，然后再遍历序列中前K个元素输出，即可，总的时间复杂度为O(nlogn + k) = O(nlogn)；——方法一

方法二–选择或者交换排序

方法三–最小堆

当然，更好的办法是维护k个元素的最大堆，原理与上述第2个方案一致，即用容量为K的最大堆存储最先遍历的K个数，并假设它们即是最小的K个数，建堆需要O(k)后，有k1）。继续遍历数列，每次遍历一个元素x，与堆顶元素比较，x），否则不更新堆。这样下来，总费时O(k+(n-k)*logk) = O(nlogk)。此方法得益于在堆中，查找等各项操作时间复杂度均为logk（不然，就如上述思路2所述：直接用数组也可以找出前k个小的元素，用时O(n*k)）；

方法四–快速排序的分治划分（中位数作为枢轴）

按编程之美第141页上解法二的所述，类似快速排序的划分方法，N个数存储在数组S中，再从数组中随机选取一个数X（随机选取枢纽元，可做到线性期望时间O(N)的复杂度），把数组划分为Sa和Sb两部分，Sa<= X <=Sb，如果要查找的K个小的元素小于Sa中的元素个数，则返回Sa中较小的K个元素，否则返回Sa中K个小的元素 + Sb中小的K-|Sa|个元素。像上述过程一样，这个运用类似快速排序的partition的快速选择Select算法寻找最小的K个元素，在最坏的情况下亦能做到O(N)的复杂度。

不过值得一提的是，这个快速选择Select算法是选择数组中“中位数的中位数”作为枢纽元，而非随机选择枢纽元；

方法五–快速排序的分治划分（随机枢轴）

Randomized-Select，每次都是随机选择数列中的一个元素作为主元，在O(n)的时间内找到第K小的元素，然后遍历输出前面的K个小的元素。如果能的话，那么总的时间复杂度为线性期望时间：O(n+k) = O(n)（当n比较小时）；

方法六–线性排序

线性时间的排序，即计数排序，时间复杂度虽能达到O(n)，但是，限制条件太多了，不常用；

方法七–最小堆与优先队列

”可以用最小堆初始化数组，然后取这个优先队列前k个值。复杂度为O(n)+k*O(logn)“。意思是针对整个数组序列建立最小堆，建堆所用时间为O(n)，然后取堆中的前k个数，即总的时间复杂度为：O(n+k*logn)。

方法八–提取最小堆的元素

与上述思路7类似，不同的是在对元素数组原地建立最小堆O(n)后，然后提取K次，但是每次提取时，换到顶部的元素只需要下移顶多K次就足够了，下移次数逐次减少（而上述思路7每次提取都需要logn，所有提取K次，思路7需要K*logn，而本思路8只需要K^2）；

代码

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; // 调试开关 #define __tmain main #ifdef __tmain #define debug cout #else #define debug 0 && cout #endif // __tmain class Solution { protected: vector
       
         m_res; public: vector
        
          GetLeastNumbers_Solution(vector
         
           numbers, int k) { m_res.clear( ); if(numbers.size( ) == 0 || numbers.size() < k) { return m_res; } // m_res.clear( ); // LeastKNumbers_BySort(numbers, k); // // m_res.clear( ); // LeastKNumbers_BySelectSort(numbers, k); // // m_res.clear( ); // LeastKNumbers_ByBubbleSort(numbers, k); LeastKNumbers_ByCountSort(numbers, k); return m_res; } /// 排序后输出前K个数字 vector
          
            LeastKNumbers_BySort(vector
           
             numbers, int k) { debug <
            
              res; sort(numbers.begin( ), numbers.end( )); for(int i = 0; i < k; i++) { debug <
             
               LeastKNumbers_BySelectSort(vector
              
                numbers, int k) { debug <
               
                 LeastKNumbers_ByCountSort(vector
                
                  numbers, int k) { int i, count; int num[1000]; memset(num, '\0', 1000); for(i = 0; i < numbers.size( ); i++) { num[numbers[i]]++; debug <
                 
                   GetLeastNumbers_ByFindKth(vector
                  
                    numbers, int k) { int kth; vector
                   
                     res; for(int i = 0; i < k; i++) { kth = FindKth(numbers, 0, numbers.size( ) - 1, i); debug <
                     &numbers, int left, int right) { int i = left, j = right; /// 我们选择第一个元素作为基准 /// 这个也可以随机选择 int pivotIndex = left, pivotNum = numbers[pivotIndex]; ddebug <<"pivotNum = " <
                     
                      = pivotNum) { ddebug <<"[" <
                      = " <
                       
                         numbers, int num) { int count = 0; for(int i = 0; i < numbers.size( ); i++) { if(numbers[i] == num) { count++; } } ddebug <<"num = " <
                        
                          numbers.size( ) / 2) { return true; } else { return false; } } class greater_class { public: bool operator()(int a, int b) { return a > b; } }; vector
                         
                           GetLeastNumbers_Solution(vector
                          
                            numbers, int k) { return LeastKNumbers_ByMinHeap(numbers, k); } vector
                           
                             LeastKNumbers_ByMinHeap(vector
                            
                              numbers, int k) { vector
                             
                               res; if(numbers.size( ) == 0 || numbers.size( ) < k) { return res; } make_heap(numbers.begin( ), numbers.end( ), greater_class()); for(int i = 0; i < k; i++) { // 最小的元素在栈顶 debug <
                              
                                vec(arr, arr + 8); Solution solu; solu.GetLeastNumbers_Solution(vec, 4); return 0; }