如何求出数组中最小（或者最大）的k个数（least k问题）

　　输入n个整数，如何求出其中最小的k个数？

解法1. 当然最直观的思路是将数组排序，然后就可以找出其中最小的k个数了，时间复杂度以快速排序为例，是O（nlogn）；

解法2. 借助划分（Partition）的思路，一次划分可以把枢轴使得枢轴左边的元素都比枢轴小，枢轴右边的元素都比枢轴大（可以参考快速排序及STL中的sort算法）。那么可以基于数组的第k个数字来调整，使得比第k个数字小的数字都位于数组的左边，使得比第k个数字大的数字都位于数组的右边。那么调整完毕后，数组中左边的k个数字就是最小的k个数字（这k个数字不一定是排序的）。该解法时间复杂度最低，是O（n），但需要修改输入的数组，如果要求不能修改输入的数组，那就行不通了。另外该算法也不大适合海量数据处理，因为没办法一次读入内存，只能一次读取一些。

　　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 <=  || start <  || 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 <=  || k <= )

        return;

    int start = ;

    int end = n - ;

    int index = Partition(input, n, start, end);

    while(index != k - )

    {

        if(index > k - )

        {

            end = index - ;

            index = Partition(input, n, start, end);

        }

        else

        {

            start = index + ;

            index = Partition(input, n, start, end);

        }

    }

    for(int i = ; i < k; ++i)

        output[i] = input[i];

}

int _tmain(int argc, _TCHAR* argv[])

{

    int data[] = {, , , , , , , , , , , , , -};

    int n = ;

    int k = ;

    int* output = new int[k];

    GetLeastNumbers(data, n, output, k);

    for (int i=; i<n; i++)

    {

        printf("%d\t", data[i]);

    }

    printf("\r\n");

    for(int i = ; i < k; ++ i)

        printf("%d\t", output[i]);

    delete[] output;

    return ;

}

解法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 <=  || start <  || 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 <  || 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[] = {, , , , , , , , , , , , , -};

    int n = ;

    int k = ;

    intSet leastNumbers;

    std::vector<int> dataVec(&data[], &data[]);// 以迭代器初始化，注意第二个参数end是最后一个元素的下一个位置

    GetLeastNumbers(dataVec, leastNumbers, k);

    for(setIterator iter = leastNumbers.begin(); iter != leastNumbers.end(); ++iter)

        printf("%d\t", *iter);

    return ;

}