找到第n大元素

Question

我需要在数组中找到第 n 个最大的元素，目前我正在按照以下方式进行操作：

std::vector<double> buffer(sequence); // sequence is const std::vector<double>
std::nth_element(buffer.begin(), buffer.begin() + idx, buffer.end(), std::greater<double>());
nth_element = buffer[idx];

但是有什么方法可以在不使用外部缓冲区的情况下找到数组中第 n 大的元素吗？

Answer 1

您可以使用快速排序中使用的分区函数来查找第 n 个最大的元素。

partition函数会将原数组一分为二parts.The第一部分会小于A[i]，第二部分会大于A[i]，partition会return i.Ifi等于n，则returnA[i]。如果i小于n，则划分第二部分part.Ifi大于n，则划分第一部分。

它不会花费你额外的缓冲，平均时间成本是O(n)。

Answer 2

您可以避免在不修改原始范围的情况下复制整个缓冲区，方法是使用 std::partial_sort_copy。只需将部分排序的范围复制到大小为 n 的较小缓冲区中，然后取出最后一个元素。

如果您可以修改原始缓冲区，那么您可以直接使用std::nth_element。