std::cout<<*iter<<'\t';
std::cout<<std::endl;
}
// if the node is not a leaf, goto its children
if(pTreeNode->m_pLeft)
FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);
if(pTreeNode->m_pRight)
FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);
// when we finish visiting a node and return to its parent node,
// we should delete this node from the path and
// minus the node's value from the current sum
currentSum -= pTreeNode->m_nValue; //!!I think here is no use
path.pop_back();
}
(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 的好印象，何乐而不为之？
参考代码：
#include <set>
#include <vector>
#include <iostream>
11
剩余63页未读，继续阅读
hero_wx
- 粉丝: 0
- 资源: 1
我的内容管理
展开
最新资源
- AirKiss技术详解：无线传递信息与智能家居连接
- Hibernate主键生成策略详解
- 操作系统实验：位示图法管理磁盘空闲空间
- JSON详解：数据交换的主流格式
- Win7安装Ubuntu双系统详细指南
- FPGA内部结构与工作原理探索
- 信用评分模型解析：WOE、IV与ROC
- 使用LVS+Keepalived构建高可用负载均衡集群
- 微信小程序驱动餐饮与服装业创新转型：便捷管理与低成本优势
- 机器学习入门指南：从基础到进阶
- 解决Win7 IIS配置错误500.22与0x80070032
- SQL-DFS：优化HDFS小文件存储的解决方案
- Hadoop、Hbase、Spark环境部署与主机配置详解
- Kisso：加密会话Cookie实现的单点登录SSO
- OpenCV读取与拼接多幅图像教程
- QT实战：轻松生成与解析JSON数据
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
