algorithm - 需要一个高效的选择算法？

Question

我正在寻找一种算法来选择 A [N/4] 未排序数组 A 中的元素，其中 N 是数组 A 的元素数。我希望算法在亚线性时间内进行选择。我有了解 BST 等基本结构？哪一个对我来说是最好的算法记住我希望它尽可能快并且对我来说不应该太难实现。这里 N 可以变化到 250000。任何帮助将不胜感激。注意数组可以有非独特元素

Answer 1

正如@Jerry Coffin 提到的，除非您愿意预先进行一些预处理，否则您不能指望在这里获得次线性时间算法。如果你想要一个线性时间算法来解决这个问题，你可以使用 quickselect algorithm ，它在 O(n²) 最坏情况下以预期的 O(n) 时间运行。 median-of-medians algorithm具有最坏情况的 O(n) 行为，但具有高常数因子。您可能会发现有用的一种算法是 introselect算法，它结合了前面的两种算法，得到一个常数因子较低的最坏情况 O(n) 算法。此算法通常用于在 C++ 标准库中实现 std::nth_element 算法。

如果你愿意提前做一些预处理，你可以把所有的元素放到一个order statistic tree中。 .从那时起，您可以在时间 O(log n) 最坏情况下查找任何 k 的第 k 个元素。不过，所需的预处理时间为 O(n log n)，因此除非您进行重复查询，否则这不太可能是最佳选择。

希望这对您有所帮助!