我正在尝试编写一个算法来返回数组中最小的'm‘元素,并且返回的元素必须按从小到大的顺序排列。
给定1<=m<=sqrt(n),其中n是数组的大小。
例如,如果数组是{8,1,12,83,33,53},而m是3,它应该返回{1,8,12} (任何形式)。
在O(N)中,我可以使用的最好的通用数据结构是什么?
我正在考虑使用Min-heap,但是我不能总是按顺序返回元素。
发布于 2014-02-28 14:14:20
从m < sqrt(n)开始,您可以按任何顺序从堆中取出元素,然后对数组进行排序。该操作的总复杂度应小于O(N)
(O(MlogM) < O(M^2) < O(N))编辑:构建堆将是一个O(NlogM)操作,因为您必须迭代整个数组。因此,如果您认为logM非常小,那么这是一个可行的解决方案。
Edit2:
This link by Jim Mischel提供了有关此问题解决方案的更多信息。
https://stackoverflow.com/questions/22087210
复制相似问题