最小的k个数

2018-03-19 技术阅读量

题

输入n个整数，找出其中最小的k个数
例：输入4、5、1、6、2、7、3、8
则最小的3个数是1、2、3

分析

首先想到最直观的解法是：将数组排序（正序），然后前面k个数字就是最小的k个数
时间复杂度就完全取决于所采用的排序算法，并且不借助辅助空间的话，排序也会对原数组的内容造成影响

思路一

递归地进行如下操作：
基于数组的第k个数来调整，比k小的数都位于数组左边，比k大的数字都位于数组右边——这样就可以使得数组前的k个数字就是最小的k个数字

思路二

创建一个大小为k的数据容器来存储最小的k个数字，接下来每次从输入的n个整数中读入一个数。如果容器中已有的数字少于k个，则直接放入；若容器中已满，则将容器中最大值与读入数字进行比较，保留更小的数在容器中

当容器满时，我们需要做3件事：

找到max
可能需要删除这个max
可能插入一个新数字

如果用一个二叉树来当容器，那么我们能在O(logk)时间内完成上述3步

我们可以选用不同的二叉树来实现。鉴于每次都要找到Max，可以使用最大堆

在最大堆中，根节点总是大于它的任意结点——可以在O(1)时间内找到Max（即为根节点）

亦可以用红黑树来实现。

红黑树通过把结点分为红、黑两种颜色并根据一些规则来保证树在一定程度上是平衡的，从而确保在红黑树中查找、删除、插入操作都只需要O(logk)时间
在STL中 set与 meltiset都是基于红黑树实现的，可以直接利用

SourceCode – C++

typedef multiset<int, greater<int>> intSet;
typedef multiset<int, greater<int>>::iterator setIterator;
void GetLeastNumber(const std::vector<int>& data, intSet& leastNumvers, int k){  
    leastNumvers.clear();

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

    std::vector<int>::const_iterator iter = data.begin();
    for(; iter != data.end(); ++iter){
      if(leastNumvers.size() < k){
        leastNumvers.insert(*iter);
      }
      else{
        setIterator iterGreatest = leastNumvers.begin();

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