什么是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.

或者,您可以尝试实现此功能的自己版本.您可以nth_element通过执行标准排序和调用来实现Collections.sort,但根据您的时间要求,这可能太慢.有许多用于执行这种重新排序的专用算法,称为选择算法,关于该主题的维基百科页面有几个很好的例子.根据经验,最快的算法称为quickselect,基于快速排序算法; 它在预期的O(n)时间内运行,但对于病理学上不良的输入可降级为O(n ²).有一种着名的(和众所周知的复杂)算法有时被称为中位数算法,在最坏情况下运行O(n),但具有高常数因子,阻止它在实践中使用.

希望这可以帮助!