java - Java 中等效的 'nth_element' 函数是什么？

Question

我不想得到排序数组，只是第 n 个元素的值。例如，给定数组

 a = [20, 5, 1, -3] 

我希望能够查询

nth_element(a,2) = 1

在 C++ 中，有一个函数 std::nth_element 可以做到这一点。是否有等效的 Java 函数？

谢谢!

Answer 1

Java 标准库不包含 C++ nth_element 算法的等价物。最接近的方法是使用 Collections.sort。

或者，您可以尝试实现您自己的此功能版本。您可以通过执行标准排序并调用 Collections.sort 来实现 nth_element，但根据您的时间要求，这可能会太慢。有许多专门的算法可以执行这种重新排序，称为选择算法 和the Wikipedia page on the subject。有几个很好的例子。根据经验，最快的算法称为 quickselect，它基于快速排序算法；它在预期的 O(n) 时间内运行，但对于病态的不良输入可能会降级为 O(n²)。有一种著名的(也是出了名的复杂)算法，有时称为中值中值算法，它在最坏情况下运行 O(n)，但具有很高的常数因子，因此无法在实践中使用。

希望这对您有所帮助!