转自 http://anwj336.blog.163.com/blog/static/89415209201010110025364/
题目:输入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)(最坏情况下需要更新n-k次)。通常情况下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);
}
}
}
}
分享到:
相关推荐
输出一组元素中的最小的k个元素。例如数据集为:{1、8、3、6、5、4、7、2},则最小的4个数字为1,2,3和4。 【基本要求】 由随机数产生测试数据,测试数据不小于10000个,测试k的不同取值对算法的影响,如k=10、50、...
可以运行的查找第K小元素的实现代码。并且实现了多个元素相同的算法。与王晓东的《算法》配套
1. 设计程序利用分治策略求n个数的最大值和最小值。 2. 利用分治策略,在n个不同元素中找出第k个最小元素。
给定一个数组 A[1...N],它找到两个给定索引之间具有最小值的元素的位置。 它在恒定时间内返回答案。 RMQ 问题可用于在恒定时间内恢复图中的 lca(最低共同祖先)。 有关更多详细信息,请参阅...
输入任意的一个网,用普里姆(Prim)算法构造最小生成树。 要求建立图的存储结构(邻接表或邻接矩阵),输入任意的一个图,显示图的深度优先搜索遍历路径。 要求建立图的存储结构(邻接表或邻接矩阵),输入任意的一个...
题目:是在一组数组(数组元素为整数,可正可负可为0)中查找乘积最大的三个数,最后输出最大乘积。 从题目我们知道只有两种结果存在: 1)三个最大的正整数相乘; 2)一个最大的正整数和两个最小的负数相乘。 所以...
在编程中非常常用的算法:计算整形数组中第k小的数
计算循环队列的元素个数:“尾指针减头指针”,若为负数,再加其容量即可。 1.5 链表 在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数据域;另一部分用于存放指针,称为指针域。其中...
查找第一个和最后一个位置 在唯一列表上搜索插入位置 大于目标的最小字母 猜数 第一个坏版本 找到多数元素 最小的公共元素 搜索已排序的二维数组 搜索未知大小 固定点 排序数组中的单个元素 等差数列中缺少数字 缺少...
项目介绍 此作业的目的是与访客一起编程。 设计一个 FileProcessor.java 类,它从输入文件中读取并在每次调用 nextInt() 方法时返回一个... 再创建两个访问者以确定 ADT 的 max-K 元素。 - 第一个访问者创建一个最大
右侧下窗口为递归工作栈,栈中每个记录含6个数据项,其中 adr 指示调用语句行号,k 指示步数,(x,y) 表示当前坐标,i 指示路径方向(起始方向为 1,顺时针方向旋转搜索)。 5. 皇后问题 左侧图示窗口包含棋盘和...
将从下标fi开始的d个元素与从下标si开始的d个元素交换;应用标准二分法快速查找数值;递归当时快速搜索转轴数;标准二分搜索算法;搜索数组中是否有“对和值”等于 x;返回下标乘积最大数;二分法搜索 low ... high ...
6.3 合并K个有序链表 6.4 使用插入排序来排序链表 6.5 归并排序排序链表 6.6 第一个缺少的正数 6.7 排序颜色 7. 查找 7.1 在排序数组中查找数出现的范围 7.2 在排序数组中查找给定值的插入位置 7.3 在二维排序数组中...
1.2 查找最小的k个元素 4 1.3 调整数组顺序使奇数位于偶数前面 5 1.4 找出数组中两个只出现一次的数字 5 1.5 旋转数组 7 1.6 旋转数组的最小元素 11 1.7 扑克牌的顺子 13 2 树 15 2.1 二叉树的非递归操作 15
查找数组中的最大和最小元素 查找数组的“第 K 个”最大值和最小值元素 给定一个只包含 0、1 和 2 的数组。在不使用任何排序算法的情况下对数组进行排序 将所有负元素移动到数组的一侧 找出两个已排序数组的并集和...
lru缓存leetcode go-leetcode Go 中 Leetcode 问题的解决方案和实现。 愿代码与你同在。 挑战完成 ...二分查找 ...K ...个排序数组中查找公共元素 : 帕斯卡三角形 : 数组排列 : 在未排序列表中查找第 k 个
算法永远是王道(含微软面试100题) (把二元查找树转变成排序的双向链表;设计包含min函数的栈;求子数组的最大和;在二元树中找出和为某一值的所有路径;查找最小的k个元素等)
注意,本题可以使用二分查找的前提是基于两个条件:一个是nums[-1] = nums[n] = -∞ ,另一个是我们只需要返回一个峰值索引。 第 658 章 找到 K 个最近的元素 中等的 好问题。 使用二分查找查找k窗口的起始索引。 ...
利用随机函数产生50个0-20之间的随机整数,存放在序列中,再通过键盘输入一个整数KEY,查找50个随机整数中是否有KEY值,如果存在,则输出他们所有的位置 题5. 回文数判断:设N是一任意自然数,如果N的各位数字反向...
FINDARRAY 在另一个数组中查找一个数组I = FINDARRAY(A,B,'first') 为数组 B 返回一个索引数组与 B 相同的大小,包含 A 中每个的最小绝对索引B 的元素是 A 的成员,如果没有这样的索引,则为 0。 FINDARRAY(A,B) 与 ...