c++ - 一意でない要素を含むソートされていない配列でk番目に大きい数を選択するための最速のアルゴリズムはどれですか？

Question

重複の可能性：
O（n）の長さnのソートされていない配列でk番目に大きい要素を見つける方法は？

要素の数は100万から1000万までさまざまです。この目的で利用できる最速の選択アルゴリズムはどれですか？配列要素が重複しているため、AVLツリーのようなデータ構造はここでは機能しないと思いますか？

Answer 1

選択アルゴリズムはO（N）時間で実行できます。

最も一般的な方法は、配列を通過させ、これまでに見たK個の最大数を維持することです。そのリストの最後の要素を返します。std::nth_element@ChrisAがコメント（ここに記載）で指摘しているように、このアプローチを使用する最も簡単な方法です。

常に上位K番目に大きいアイテムが必要な場合（およびデータが時々変更される場合）、データをヒープに格納することを検討してください。これはより高価ですが、データの「ライブ」構造を提供します。

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番目に大きい場合は、引数を1つか2つ追加する必要があります。これは、今日の後半に行います。