假设我们在一个数组中有一个大数据集（比如 50000），我们现在想要获取数组中前 50 个最高的数字，您是否建议使用优先级队列并弹出 50 次？将数组中的 50000 个元素中的每一个插入优先级队列最多可能需要 O(n)，如果你这样做 50000 次，它就会变成 O(n^2)，这很昂贵。如何获得更好的 O 复杂度？
问问题
744 次
1 回答
4
您可以使用nth_element查找平均复杂度为 ~O(n) 的前 50 个元素，然后根据需要对数组的 50 个初始索引进行排序。
或者，您可以遍历数组，将项目放入单独的 priority_queue 中，只要您的元素少于 50 个，或者当前项目高于第 50 个元素。只要你有 51 个元素，你就会弹出一个。最坏情况 O(n*log(50))。
最后一件事，如果数组中的所有值都低于某个限制，例如 <= 10^5，则可以使用桶排序。只需遍历整个数组，然后执行++bucket[array[i]];. 然后你线性迭代bucket记下你找到的 50 个最小的数字。最坏情况O(n) + O(m)，其中 m = 数组中的最大值。
于 2013-05-24T05:25:36.657 回答