0

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

4

1 回答 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 回答