python - 查找数组中第 n1 个最小数字到第 n2 个最小数字的快速算法

Question

我有一个数组，我试图找到数组中第 n1 个最小的数字，直到第 n2 个最小的数字，并将它们存储在另一个大小为 n2-n1+1。这里的n2n1与数组的大小相比都非常小(比如数组大小为10000，n1=5 , n2=20)。

我可以先对这个数组进行排序，然后从中取出第n1、n1+1直到第n2个数排序的数组。但是由于 n1 和 n2 与数组的大小相比通常相对较小，因此没有必要对数组进行完全排序。一旦达到 n2 我认为该算法应该能够在中间停止。

我想知道是否有任何算法，也许是 certian 排序算法的修改版本，在这个问题上特别好(好的，我的意思是快)。您可以使用 Python 代码或伪代码作为示例，谢谢!

Answer 1

因为，与数组的大小相比，N1 和 N2 确实很小，让我们说 N。我们可以使用最小堆数据结构在 O(N2 * LogN) 中实现。

步骤

1. 构造一个最小堆。此操作的复杂度为 O(N)
2. 循环 0 到 N2 的范围: 获取根元素并调用 heapify。忽略前 N1 个元素并返回其余元素。这一步的复杂度是 O(1)+O(logN)因此，总的来说我们有 O(N2 * logN)