0

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

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

4

2 に答える 2

6

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

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

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

于 2012-07-10T11:13:39.560 に答える
0

これは、このコードを使用してコンパイル時に実行できます(最新の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つ追加する必要があります。これは、今日の後半に行います。

于 2012-07-10T11:25:15.313 に答える