[剑指offer]数组中最小的K个数，C++实现

原创博文，转载请注明出处！

http://github.com/wanglei5205

http://cnblogs.com/wanglei5205

# 题目

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4

# 思路

基于Partition的思路

时间复杂度为O(n)

基于红黑树的思路

　　辅助容器：定义用于遍历向量的辅助容器--迭代器ite；定义用于存储结果的辅助容器--多重集合res。

基本思路：首先创建一个大小为k的容器，用来存储最小的k个数字；然后每次从输入的n个整数中输入一个数，如果容器中已有的数字少于k个，则直接把读入的整数放入容器；如果容器中已有k个数字，则不能再插入新的数字而只能替换已有的数字。替换的原则：如果待插入的值m比容器中的最大值n小，则m替换n；如果待插入的值m比容器中的最大值n大，则保持不变。（在k个整数中找到最大值、删除容器最大值、插入一个新的数字）

时间复杂度：O(n*logk)

# 代码

1.基于partition的思路

2.基于红黑树的思路

  1 // 使用红黑树实现
  2 class Solution {
  3 public:
  4     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
  5         // 特殊输入
  6         if(input.size()<=0||k>input.size()) return vector<int>();
  7 
  8         // 定义降序排列的集合res，用于存储结果
  9         multiset<int, greater<int> > res;
 10 
 11         // 定义遍历向量的迭代器ite，遍历向量vector
 12         vector<int>::iterator cur_ite;
 13         for(cur_ite = input.begin();cur_ite!=input.end();++cur_ite)
 14         {
 15             // 将前k个元素插入集合
 16             if(res.size()<k)
 17                 res.insert(*cur_ite);
 18             else
 19             {
 20                 // 比较+删除+插入
 21                 if(*cur_ite<*(res.begin()))
 22                 {
 23                     res.erase(res.begin());
 24                     res.insert(*cur_ite);
 25                 }
 26             }
 27         }
 28         return vector<int>(res.begin(),res.end());
 29     }
 30 };