题
输入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++
1 | typedef multiset<int, greater<int>> intSet; |