哪个是在包含非唯一元素的未排序数组中选择第k个最大数字的最快算法？
可能重复：
如何在O（n）中找到长度为n的未排序数组中的第k个最大元素？
元素数量可以在1到1千万之间变化。这是最快的选择算法吗？ 请注意我认为由于数组元素的重复，像AVL Trees这样的数据结构在这里不起作用？
选择算法可以在O（N）时间内运行。
最常见的方法是通过数组，保持你目前为止看到的K个最大数字。 返回该列表的最后一个元素。 正如@ChrisA在评论中指出的那样， std::nth_element （ 此处记录 ）是使用此方法的最快方法。
如果您总是想要最大的Kth项（并且有时会更改数据），那么请考虑将数据存储在堆中 。 这样更昂贵，但为您提供了数据的“实时”结构。
这可以在编译时使用此代码完成（请记住，您需要最新的GCC或Clang，此时不能在MSVC2k12中工作）。 它使编译速度变慢，但它在运行时是即时的。
#include constexpr int array[10] = { 1, 0, 2, 3, 0, 2, 7, 1, 9, 2 }; template struct find_biggest_r { enum { value = find_biggest_r<(array[index] > maxest ? array[index]:maxest),index-1>::value }; }; template struct find_biggest_r { enum { value = (array[0] > maxest ? array[0] : maxest) }; }; template struct find_biggest { enum { value = find_biggest_r::value }; }; int main() { std::cout << find_biggest<10>::value; }
编辑：对不起，这只是最大的。 对于第k个最大的，我需要添加一个或两个参数，我将在今天晚些时候进行。