c++ - 在包含非唯一元素的未排序数组中选择第 k 个最大数的最快算法是什么？

Question

可能重复：
如何在 O(n) 中找到长度为 n 的未排序数组中的第 k 个最大元素？

元素的数量可以从 1 到 1000 万不等。可用于此目的的最快选择算法是什么？请注意，由于数组元素的重复，我认为像 AVL 树这样的数据结构在这里不起作用？

Answer 1

选择算法可以在 O(N) 时间内运行。

最通用的方法是通过数组，保留迄今为止你见过的最大的 K 个数字。返回该列表的最后一个元素。正如@ChrisA 在评论中指出的那样std::nth_element（在此处记录）是使用这种方法的最快方法。

如果您总是想要前 Kth 最大的项目（并且数据有时会更改），那么请考虑将数据存储在heap中。这更昂贵，但为您提供了数据的“实时”结构。

Answer 2

这可以在编译时使用此代码完成（请记住，您需要最新的 GCC 或 Clang，此时在 MSVC2k12 中不起作用）。它使它编译缓慢，但在运行时是即时的。

#include <iostream>

constexpr int array[10] = { 1, 0, 2, 3, 0, 2, 7, 1, 9, 2 };

template<int maxest, int index>
struct find_biggest_r {
  enum { value = find_biggest_r<(array[index] > maxest ? array[index]:maxest),index-1>::value };
};

template<int maxest>
struct find_biggest_r<maxest,0> {
 enum { value = (array[0] > maxest ? array[0] : maxest) };
};

template<int index>
struct find_biggest {
  enum { value = find_biggest_r<array[index-1],index-2>::value };
};

int main()
{
    std::cout << find_biggest<10>::value;
}

编辑：对不起，这只是最大的。对于第 k 个最大的，我需要添加一两个参数，我将在今天晚些时候做。