我正在寻找一种算法来选择 A [N/4] 未排序数组 A 中的元素，其中 N 是数组 A 的元素数。我希望算法在次线性时间内进行选择。我有基本的知识BST等结构？哪一个对我来说是最好的算法，记住我希望它是最快的，并且对我来说实施起来不应该太难。这里 N 可以变化到 250000。任何帮助将不胜感激。注意数组可以有非独特的元素
问问题
260 次
1 回答
2
正如@Jerry Coffin 提到的，除非您愿意预先进行一些预处理，否则您不能希望在这里获得次线性时间算法。如果你想要一个线性时间算法来解决这个问题，你可以使用快速选择算法，它在预期的 O(n) 时间内运行，最坏的情况是 O(n 2 )。中位数算法具有最坏情况的 O(n) 行为，但具有较高的常数因子。您可能会发现一种有用的算法是introselect算法，它结合了前面的两种算法以获得具有低常数因子的最坏情况 O(n) 算法。该算法通常用于std::nth_element在 C++ 标准库中实现该算法。
如果您愿意提前进行一些预处理，您可以将所有元素放入一个订单统计树中。从那时起，您可以在 O(log n) 最坏情况下查找任何 k 的第 k 个元素。但是，所需的预处理时间为 O(n log n)，因此除非您进行重复查询，否则这不太可能是最佳选择。
希望这可以帮助！
于 2012-07-07T22:14:25.060 回答