如何求出數組中最小（或者最大）的k個數（least k問題）

　　輸入n個整數，如何求出其中最小的k個數？

解法1. 當然最直觀的思路是將數組排序，然後就可以找出其中最小的k個數了，時間複雜度以快速排序為例，是O（nlogn）；

解法2. 藉助劃分（Partition）的思路，一次劃分可以把樞軸使得樞軸左邊的元素都比樞軸小，樞軸右邊的元素都比樞軸大（可以參考快速排序及STL中的sort演算法）。那麼可以基於數組的第k個數字來調整，使得比第k個數字小的數字都位於數組的左邊，使得比第k個數字大的數字都位於數組的右邊。那麼調整完畢後，數組中左邊的k個數字就是最小的k個數字（這k個數字不一定是排序的）。該解法時間複雜度最低，但需要修改輸入的數組，如果要求不能修改輸入的數組，那就行不通了。另外該演算法也不大適合海量數據處理，因為沒辦法一次讀入記憶體，只能一次讀取一些。

　　C++代碼如下：

#include "stdafx.h"
#include <set>
#include <vector>
#include <iostream>

using namespace std;
int Partition(int data[], int length, int start, int end)
{
    if(data == NULL || length <= 0 || start < 0 || end >= length)
        throw new std::exception("Invalid Parameters");

    int pivotkey = data[start];// 記錄樞軸關鍵字
    while (start < end)
    {
        while(start<end && data[end]>=pivotkey) 
            --end;// 找到從end位置開始向前第一個比樞軸小的元素
        data[start] = data[end];// 將找到的比樞軸小的元素放到前邊的空閑位置
        while(start<end && data[start]<=pivotkey) 
            ++start;// 找到從start位置開始向後第一個比樞軸大的元素
        data[end] = data[start];// 將找到的比樞軸大的元素放到後邊的空閑位置
    }
    data[start] = pivotkey;// 將樞軸放回中間的空閑位置

    return start;
}

void GetLeastNumbers(int* input, int n, int* output, int k)
{
    if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
        return;

    int start = 0;
    int end = n - 1;
    int index = Partition(input, n, start, end);
    while(index != k - 1)
    {
        if(index > k - 1)
        {
            end = index - 1;
            index = Partition(input, n, start, end);
        }
        else
        {
            start = index + 1;
            index = Partition(input, n, start, end);
        }
    }

    for(int i = 0; i < k; ++i)
        output[i] = input[i];
}

int _tmain(int argc, _TCHAR* argv[])
{
    int data[] = {4, 5, 1, 6, 2, 7, 3, 0, 100, 8, 4, 2, 8, -1};
    int n = 14;
    int k = 4;
    int* output = new int[k];
    GetLeastNumbers(data, n, output, k);

    for (int i=0; i<n; i++)
    {
        printf("%d\t", data[i]);
    }
    printf("\r\n");
    for(int i = 0; i < k; ++ i)
        printf("%d\t", output[i]);
    delete[] output;
    return 0;
}

解法3. 在本地維護好一個大小為k的容器，該容器能夠進行自動排序，能夠自動排序的容器可以選擇STL中的set和multiset，因為它們內部是基於紅黑樹來實現的，每次插入刪除都會進行自動調整。依次讀取數組中的一個新元素，與容器中最大的元素做比較，如果小於容器中的最大的元素，則將該最大元素替換，這樣迴圈一遍需要O（n）的複雜度，每次容器進行調整平均是O（logk），這樣該演算法最終的時間複雜度是O（nlogk）。顯而易見，該演算法不需要修改原始數據，且適合海量數據處理。

　　C++代碼如下：

#include "stdafx.h"
#include <set>
#include <vector>
#include <iostream>

using namespace std;
int Partition(int data[], int length, int start, int end)
{
    if(data == NULL || length <= 0 || start < 0 || end >= length)
        throw new std::exception("Invalid Parameters");

    int pivotkey = data[start];// 記錄樞軸關鍵字
    while (start < end)
    {
        while(start<end && data[end]>=pivotkey) 
            --end;// 找到從end位置開始向前第一個比樞軸小的元素
        data[start] = data[end];// 將找到的比樞軸小的元素放到前邊的空閑位置
        while(start<end && data[start]<=pivotkey) 
            ++start;// 找到從start位置開始向後第一個比樞軸大的元素
        data[end] = data[start];// 將找到的比樞軸大的元素放到後邊的空閑位置
    }
    data[start] = pivotkey;// 將樞軸放回中間的空閑位置

    return start;
}

typedef multiset<int, greater<int> >            intSet;
typedef multiset<int, greater<int> >::iterator  setIterator;

void GetLeastNumbers(const vector<int>& data, intSet& leastNumbers, int k)
{
    leastNumbers.clear();

    if(k < 1 || data.size() < k)
        return;

    vector<int>::const_iterator iter = data.begin();
    for(; iter != data.end(); ++ iter)
    {
        if((leastNumbers.size()) < k)
            leastNumbers.insert(*iter);

        else
        {
            setIterator iterGreatest = leastNumbers.begin();

            if(*iter < *(leastNumbers.begin()))
            {
                leastNumbers.erase(iterGreatest);
                leastNumbers.insert(*iter);
            }
        }
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    int data[] = {4, 5, 1, 6, 2, 7, 3, 0, 100, 8, 4, 2, 8, -1};
    int n = 14;
    int k = 4;
    intSet leastNumbers;

    std::vector<int> dataVec(&data[0], &data[14]);// 以迭代器初始化，註意第二個參數end是最後一個元素的下一個位置
    GetLeastNumbers(dataVec, leastNumbers, k);

    for(setIterator iter = leastNumbers.begin(); iter != leastNumbers.end(); ++iter)
        printf("%d\t", *iter);

    return 0;
}