題意

---

題目描述

輸入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個數，甚至是後面的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)，整趟下來，總的時間復雜度平均下來為：n*O(k) = O(n*k)；——方法二

方法三–最小堆

---

當然，更好的辦法是維護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;
}