首页 > 代码库 > IT公司100题-5

IT公司100题-5

题目:输入n个整数,输出其中最小的k个。 
例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。 
分析:这道题最简单的思路莫过于把输入的n个整数排序,这样排在最前面的k个数就是最小的k个数。只是这种思路的时间复杂度为O(nlogn)。我们试着寻找更快的解决思路。 
我们可以开辟一个长度为k的数组。每次从输入的n个整数中读入一个数。如果数组中已经插入的元素少于k个,则将读入的整数直接放到数组中。否则长度为k的数组已经满了,不能再往数组里插入元素,只能替换了。如果读入的这个整数比数组中已有k个整数的最大值要小,则用读入的这个整数替换这个最大值;如果读入的整数比数组中已有k个整数的最大值还要大,则读入的这个整数不可能是最小的k个整数之一,抛弃这个整数。这种思路相当于只要排序k个整数,因此时间复杂可以降到O(n+nlogk)。通常情况下k要远小于n,所以这种办法要优于前面的思路。 
这是我能够想出来的最快的解决方案。不过从给面试官留下更好印象的角度出发,我们可以进一步把代码写得更漂亮一些。从上面的分析,当长度为k的数组已经满了之后,如果需要替换,每次替换的都是数组中的最大值。在常用的数据结构中,能够在O(1)时间里得到最大值的数据结构为最大堆。因此我们可以用堆(heap)来代替数组。 
另外,自己重头开始写一个最大堆需要一定量的代码。我们现在不需要重新去发明车轮,因为前人早就发明出来了。同样,STL中的set和multiset为我们做了很好的堆的实现,我们可以拿过来用。既偷了懒,又给面试官留下熟悉STL的好印象,何乐而不为之? 
参考代码:

#include <set>#include <vector>#include <iostream>using namespace std;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);                   }             }       }}