arrays - 返回输入数组的前 K 个元素

Question

我正在寻找从输入数组中返回前 k 元素的有效方法。
一种方法是对数组进行排序并从数组末尾返回 k 元素。

还有其他方法建议here ，其中一个使用 quickselect 算法，但据我了解，quickselect 仅返回未排序数组中的第 k 个元素。返回后，k 左右两侧的元素仍未排序。

所以它应该是这样的:

while k>0{
   quickselect(int[] arr, k);
   k--;
}

Quickselect 是 O(n)，我们这样做了 k 次，所以整体时间复杂度是 O(n*k) .
但是帖子中的数据表明这比 O(n log n) 更好。
从一百万个样本中选择前 200 个，在前者中意味着 2 亿，而在后者中则意味着 2000 万。显然，这要好得多。

我对如何使用快速选择来选择前 200 个元素的理解是否正确？

Answer 1

不，您不需要 O(nk) 时间 - 它可以在 O(n) 内完成(平均情况)。

---

quickselect 的最终结果将是数组中距离末尾第 k 个位置的第 k 个元素，左边是较小的元素，右边是较大的元素。

所以从那个元素到右边的所有元素都将是 k 个最大的元素 - 在 O(k) 中提取这些元素是微不足道的(使用简单的 for 循环)，这将结束总运行时间为 O(n)。

---

或者，由于您在运行快速选择后知道第 k 个元素，因此您可以再次遍历数组并提取大于或等于该元素的所有元素(这可以一次性完成 - 也可以 O(n)).

---

如果你想按排序的顺序返回它们，你需要额外的 O(k log k) (对它们进行排序)。