C＃：N×N行列で最大のm要素を見つける効率的なアルゴリズム

Question

このようなメソッドヘッダーを持つN x N行列で最大のm要素を見つける効率的なアルゴリズムがあるかどうかを知りたいと思います。

double[] greatestValues(double[][] matrix, int numberOfElements); 

Answer 1

あなたはN×N個のアイテムの配列としてN×N個の行列を扱う場合は、次のいずれかの方法を適用することができます。

クイックソートに基づく選択アルゴリズム迅速 ソートの直接適用要素を使用して、k最小またはk最大 要素を見つけることができます。 k個の最小要素を見つけるには を使用してk番目の最小要素を見つけ、中央値のクイックソートベースのアルゴリズム を求めます。 はk番目の最小の要素を見つけることパーティション後、k番目 小さい要素よりも小さい全て 要素はk番目の最小の要素に存在右あろうk番目の要素とすべての要素 大きなに左存在するであろう。したがって、すべて 要素は、第1〜第k要素 を含み、k最小の 要素を構成します。時間の複雑さはnで直線 であり、合計数は です。

データ構造ベースのソリューション別の簡単な方法は、ほとんどのk個の要素でヒープまたは 自動平衡二分探索木、 と同様に、順序付けられた セットのデータ構造にリストの各 要素を追加することです。 データ構造体にk個以上の要素がある場合は、最大の 要素を削除します。この要素は、O（log k） 時間で実行できます。各挿入操作も はO（log k）時間かかるので、結果的にO（nlog k）時間が になります。

優先 キュー内の場所の要素を修飾 幅優先探索アルゴリズムを使用してヒープトラバースΘ（n）の時間でヒープにリスト を変換し、その後 することが可能である（代わりに 通常はBFSで使用されます）、 は、正確にk個の要素を にトラバースした後にスキャンを終了します。待ち行列サイズ がトラバーサル全体にわたってO（k）のままであるので、 は、 までのO（klog k）時間を必要とし、このアルゴリズムでは O（n + klog k）の時間制限につながる。

here。