程序员面试50题(1)—查找最小的k个元素[算法]

题目:输入n个整数,输出其中最小的k个。例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。

分析:这道题最简单的思路莫过于把输入的n个整数排序,这样排在最前面的k个数就是最小的k个数。只是这种思路的时间复杂度为O(nlogn)。我们试着寻找更快的解决思路。

我们可以先创建一个大小为k的数据容器来存储最小的k个数字。接下来我们每次从输入的n个整数中读入一个数。如果容器中已有的数字少于k个,则直接把这次读入的整数放入容器之中;如果容器中已有k个数字了,也就是容器已满,此时我们不能再插入新的数字而只能替换已有的数字。我们找出这已有的k个数中最大值,然和拿这次待插入的整数和这个最大值进行比较。如果待插入的值比当前已有的最大值小,则用这个数替换替换当前已有的最大值;如果带插入的值比当前已有的最大值还要大,那么这个数不可能是最小的k个整数之一,因为我们容器内已经有k个数字比它小了,于是我们可以抛弃这个整数。

因此当容器满了之后,我们要做三件事情:一是在k个整数中找到最大数,二是有可能在这个容器中删除最大数,三是可能要插入一个新的数字,并保证k个整数依然是排序的。如果我们用一个二叉树来实现这个数据容器,那么我们能在O(logk)时间内实现这三步操作。因此对于n个输入数字而言,总的时间效率就是O(nlogk)。

我们可以选择用不同的二叉树来实现这个数据容器。由于我们每次都需要找到k个整数中的最大数字,我们很容易想到用最大堆。在最大堆中,根结点的值总是大于它的子树中任意结点的值。于是我们每次可以在O(1)得到已有的k个数字中的最大值,但需要O(logk)时间完成删除以及插入操作。

我们自己从头实现一个最大堆需要一定的代码。我们还可以采用红黑树来实现我们的容器。红黑树通过把结点分为红、黑两种颜色并根据一些规则确保树是平衡的,从而保证在红黑树中查找、删除和插入操作都只需要O(logk)。在STL中set和multiset都是基于红黑树实现的。如果面试官不反对我们用STL中的数据容器,我们就直接拿过来用吧。下面是基于STL中的multiset的参考代码:

typedef multiset<int, greater<int> >  IntHeap;

///////////////////////////////////////////////////////////////////////
// find k least numbers in a vector
///////////////////////////////////////////////////////////////////////
void FindKLeastNumbers
(
      const vector<int>& data,               // a vector of data
      IntHeap& leastNumbers,                 // k least numbers, output
      unsigned int k                              
)
{
      leastNumbers.clear();

      if(k == 0 || data.size() < k)
            return;

      vector<int>::const_iterator iter = data.begin();
      for(; iter != data.end(); ++ iter)
      {
            // if less than k numbers was inserted into leastNumbers
            if((leastNumbers.size()) < k)
                  leastNumbers.insert(*iter);

            // leastNumbers contains k numbers and it's full now
            else
            {
                  // first number in leastNumbers is the greatest one
                  IntHeap::iterator iterFirst = leastNumbers.begin();

                  // if is less than the previous greatest number 
                  if(*iter < *(leastNumbers.begin()))
                  {
                        // replace the previous greatest number
                        leastNumbers.erase(iterFirst);
                        leastNumbers.insert(*iter);
                  }
            }
      }
}

原文

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1200 同余方程

1200 同余方程 2012年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目...

2874
来自专栏take time, save time

你所能用到的数据结构(四)

五、如何递,怎样归? 很多人看完递归的原理之后会有这种感觉,喔,这个原理我懂了,然后再找一道其余的题目看一看能不能写的出来,突然发现,我勒个去,还是不会。其实...

34410
来自专栏HTML5学堂

游戏开发 - Math对象相关知识讲解

前几期小编给大家总结了JavaScript的基础知识,为我们后期深入学习JS打下了一定的基础。在后面的几期文章当中我们要来进行JS小游戏的开发,但是开发小游戏的...

29810
来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

2862
来自专栏IT可乐

深入理解计算机系统(2.6)------整数的运算

  前面两篇博客我们详细讲解了计算机中整数的表示,包括有符号和无符号(补码编码)的详细介绍。那么这篇博客我们将对它们的运算有个详细的了解。   在讲解之前首先看...

2727
来自专栏灯塔大数据

每周学点大数据 | No.22 外排序

No.22期 外排序(一) Mr. 王:接下来我们看一看在磁盘算法中一个比较典型的例子——外排序。 小可:那什么又是外排序呢? Mr. 王:外排序是相...

3746
来自专栏海天一树

小朋友学算法(6):求幂pow函数的四种实现方式

在math.h中,声明了一个函数pow(x, n),用于求x的n次方。 假如咱们不调用math.h中的pow函数,如何实现求x ^ n的算法呢?

1922
来自专栏玄魂工作室

Python数据结构与算法-在M个数中找K个最小的数

比如输入10,-9,0,100,90,1,4,-9;找到最小的3个数为:-9,-9,0

2441
来自专栏前端儿

A+B Problem(V)

做了A+B Problem之后,Yougth感觉太简单了,于是他想让你求出两个数反转后相加的值。帮帮他吧

851
来自专栏互联网大杂烩

快速排序

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值...

752

扫码关注云+社区

领取腾讯云代金券