`

程序员面试题精选(05)-查找最小的k个元素

阅读更多

题目:输入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的好印象,何乐而不为之?
参考代码:

C++代码 复制代码
  1. #include <set>   
  2. #include <vector>   
  3. #include <iostream>   
  4. using namespace std;   
  5. typedef multiset<int, greater<int> >   IntHeap;   
  6. ///////////////////////////////////////////////////////////////////////   
  7. // find k least numbers in a vector   
  8. ///////////////////////////////////////////////////////////////////////   
  9. void FindKLeastNumbers   
  10. (   
  11.       const vector<int>& data,               // a vector of data   
  12.        IntHeap& leastNumbers,                 // k least numbers, output   
  13.       unsigned int k                                 
  14. )   
  15. {   
  16.        leastNumbers.clear();   
  17.   
  18.       if(k == 0 || data.size() < k)   
  19.             return;   
  20.        vector<int>::const_iterator iter = data.begin();   
  21.       for(; iter != data.end(); ++ iter)   
  22.        {   
  23.             // if less than k numbers was inserted into leastNumbers   
  24.             if((leastNumbers.size()) < k)   
  25.                    leastNumbers.insert(*iter);   
  26.   
  27.             // leastNumbers contains k numbers and it's full now   
  28.             else  
  29.              {   
  30.                   // first number in leastNumbers is the greatest one   
  31.                    IntHeap::iterator iterFirst = leastNumbers.begin();   
  32.                   // if is less than the previous greatest number    
  33.                   if(*iter < *(leastNumbers.begin()))   
  34.                    {   
  35.                         // replace the previous greatest number   
  36.                          leastNumbers.erase(iterFirst);   
  37.                          leastNumbers.insert(*iter);   
  38.                    }   
  39.              }   
  40.        }   
  41. }  
#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);
                   }
             }
       }
}

 

分享到:
评论

相关推荐

    程序员面试题精选100题-何海涛

    《程序员面试题精选100题—何海涛》是一份详实的IT面试准备资料,由何海涛整理发布,旨在帮助应届毕业生和求职者准备面向微软、谷歌等知名科技公司的面试。此资料不仅收录了精选的100道面试题目,还提供了详细的解题...

    程序员面试题精选100题

    程序员面试题精选 100 题(01)-把二元查找树转变成排序的 双向链表 题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点, 只调整指针的指向。 程序员面试题精选 100 题...

    程序员面试题精选100题.doc

    对于程序员面试,理解并能熟练应用这类问题的解决方案,展示了解数据结构和算法的能力,是评估应聘者编程技能的重要标准。同时,能清晰解释和分析递归过程,也是考察逻辑思维和问题解决能力的关键。

    程序员面试题精选(1-57)

    本资源"程序员面试题精选(1-57)"显然是一个汇集了众多面试题目的集合,涵盖了从基础到高级的各种问题,旨在帮助求职者提升自己的技能并顺利通过面试。 首先,我们要理解数据结构的重要性。数据结构是组织和存储数据...

    程序员面试题精选100题【数据结构 /算法】

    【程序员面试题精选100题【数据结构 /算法】】是针对求职程序员精心挑选的一系列面试题目,涵盖了数据结构和算法两大核心领域。这些题目旨在帮助应聘者提高面试技巧,提升对技术的理解,以便在激烈的就业市场竞争中...

    程序员面试题精选100题完整版

    本题要求将二叉查找树转化为一个排序的双向链表,这一转换不仅考验应聘者对二叉树特性的理解,同时也考察了其对链表操作的熟练程度。 #### 1.2 题目描述 题目要求输入一棵二叉查找树,并将其转换为一个排序的双向...

    程序员面试题精选100题.docx

    本文档概述了程序员面试题精选100题,涵盖了C++面试题和笔试题,其中有一道典型的题目是将二元查找树转换成排序的双向链表。 知识点一:二元查找树(Binary Search Tree) * 二元查找树是一种特殊的树数据结构,它...

    程序员面试题精选100题(自己整理)

    【知识点详解】 1. **二元查找树(Binary Search ... 这类问题通常出现在程序员的面试中,因为它测试了对数据结构的理解、递归思维以及解决问题的能力。理解和掌握这个问题的解法对于提升编程技巧和面试表现至关重要。

    程序员面试题精选100题.pdf

    这里我们重点讨论的是如何将一个二元查找树(Binary Search Tree, BST)转换成一个排序的双向链表,这是一个典型的面试题,考察了对数据结构的理解和递归算法的应用。 二元查找树是一种特殊的二叉树,每个节点的值...

    程序员面试题精选100题(更新至60)

    例如,本文提到的《程序员面试题精选100题》就旨在为即将进入职场的程序员提供一系列经典的技术面试题目,帮助他们系统地复习相关知识和技术要点,从而提升面试表现。 #### 4. 具体案例分析:将二叉查找树转化为...

Global site tag (gtag.js) - Google Analytics