首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >数据结构来寻找O(N)中的m个最小元素?

问数据结构来寻找O(N)中的m个最小元素?
EN

Stack Overflow用户
提问于 2014-02-28 13:43:27
回答 1查看 466关注 0票数 0

我正在尝试编写一个算法来返回数组中最小的'm‘元素,并且返回的元素必须按从小到大的顺序排列。

给定1<=m<=sqrt(n),其中n是数组的大小。

例如,如果数组是{8,1,12,83,33,53},而m是3,它应该返回{1,8,12} (任何形式)。

在O(N)中,我可以使用的最好的通用数据结构是什么?

我正在考虑使用Min-heap,但是我不能总是按顺序返回元素。

EN

回答 1

Stack Overflow用户

发布于 2014-02-28 14:14:20

从m < sqrt(n)开始,您可以按任何顺序从堆中取出元素,然后对数组进行排序。该操作的总复杂度应小于O(N)

代码语言:javascript
复制
(O(MlogM) < O(M^2) < O(N))

编辑:构建堆将是一个O(NlogM)操作,因为您必须迭代整个数组。因此,如果您认为logM非常小,那么这是一个可行的解决方案。

Edit2:

This link by Jim Mischel提供了有关此问题解决方案的更多信息。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/22087210

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档