查找最小的K个数

输出最小的K个数
方案1:如果输入的数组可变,我们可以借助Partion部分排序的思想,随机选k值,经过排序后,k左边的数都比k小,k右边的数都比k大,这样经过排序后,在k左边的数字就是最小的K个数:

int Partion(int*a, int n, int left, int right)
{
    if (a == NULL || n <= 0)
    {
        return 0;
    }
    if(left >= right)
    {
        return 0;
    }
    int key = a[right];
    while (left < right)
    {
        if (left < right&&a[left] <= key)
        {
            ++left;
        }
        a[right] = a[left];
        if (left < right&&a[left] >= key)
        {
            --right;
        }
        a[right] = a[left];
    }
    a[left] = key;
    return left;
}
void GetlastNums(int*Input, int n, int *Out, int k)
{
    if (Input == NULL || Out == NULL || n < k)
    {
        return;
    }
    int begin = 0;
    int end = n - 1;
    int index = Partion(Input, n, begin, end);
    while(index!=k-1)
    {
        if (index>k - 1)
        {
            //最小的k个数在中位数左边
            end = index - 1;
            index = Partion(Input, n, begin, end);
        }
        else
        {
            //最小的K个数在中位数的右边
            begin = index + 1;
            index = Partion(Input, n, begin, end);

    }
    for (int i = 0; i < k; i++)
        Out[i] = Input[i];
}

但是方案一有明显的限制:我们需要修改输入的数组,因为,Partion会改变数组的数字的顺序,如果不修改数组的顺序该如何呢?
方案二:适合海量数据的处理
我们先建一个大小为K个元素数据的容器用来存储最小的Ｋ个数，接下来每次从输出的ｎ个数据的整数中读取一个数，如果容器里面的元素的个数小于ｋ，直接将输出的元素插入到容器里面，如果容器里面的元素个数已经是ｋ，表明容器已经满了，此时比较下一个插入的数字与容器的元素的最大值比较，小，用这个数字替换容器中的最大的元素，如果大，直接抛弃，直到输入的元素全部插入容器

我们发现容器满了会做三件事：一是在ｋ个整数中找最大的数，二是有可能在这个容器中删除最大的数，三：可能要插入一个新的数字
这时我们很容易想到大堆，堆顶是最大元素，其他的元素都比堆顶要小，取堆顶的元素时间复杂度是Ｏ（１），堆的插入和删除时间复杂度nlgn,如果用二叉树来做总的效率就是nlgK
但是有个缺点就是插入和删除都要重新调整堆

我们想到了红黑树,红黑树的插入,查找,删除的效率都是lgn
在STL中set和multiset都是基于红黑树实现

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include <functional>
using namespace std;
typedef multiset<int, std::greater<int>> inset;
typedef multiset<int, std::greater<int>> ::iterator setiter;

void _GetleaseNum(vector<int>&data, inset&Leasenum, int k)
{

    if (data.size() < k || k < 1)
    {
        return;
    }
    vector<int>::iterator it = data.begin();//迭代器遍历输入的数组
    for (; it < data.end(); it++)
    {
        if (Leasenum.size() < k)
        {
            //当容器里面的元素小于k时
            Leasenum.insert(*it);
        }
        else
        {
            //此时容器已经满了
            setiter itrgreater = Leasenum.begin();//找到容器里面最大的元素
            if (*Leasenum.begin()>(*it))
            {
                Leasenum.erase(itrgreater);//删除最大的元素
                Leasenum.insert(*it);//然后插入
            }
        }
    }
}