6

私はこの問題にかなり頻繁に遭遇します。シーケンスが与えられた場合、k 最小の要素を見つけます。問題はそれほど難しいことではありませんが、私が探しているのは、両方とも安全な「慣用的な」方法です (エラー）、意図をうまく伝えます。したがって、最終的に行うことは、シーケンスをソートしてから、最初の k 要素を取得することです。

std::sort(container.begin(),container.end());
std::vector<T> k_smallest(container.begin(),container.begin() + k);

これは安全で理解しやすいように思えますが、ここでの複雑さは単に n ではなく nlogn + k です。皆さんはこれをどのように行いますか、車輪を再実装することなく最適な複雑さを与える、(多分からいくつかのあいまいな関数を使用して) 偶像的な方法はありますか?

4

3 に答える 3

16

std :: nth_element（） -平均して線形の複雑さ。

nth_element[first、last）の要素を次のように再配置する部分ソートアルゴリズムです。

  • n番目が指す要素は、[first、last）がソートされた場合に、その位置で発生する要素に変更されます。
  • この新しいn番目の要素の前のすべての要素は、新しいn番目の要素の後の要素以下です。
于 2012-03-14T15:06:44.357 に答える
7

partial_sort()を見たいと思うかもしれません

sort()これは理解しやすく、追加の作業を必要とせず、k 番目の要素だけを気にする場合はより良い [または少なくともそれより悪くはない] と予想されます。

最適なパフォーマンスを得るには、選択アルゴリズムを使用することをお勧めしますが、より多くの作業が必要です。

于 2012-03-14T15:04:14.823 に答える
1

最初のアルゴリズム:

手順:

複雑さ: O(n) 最悪のケース

2 番目のアルゴリズム:

手順:

  • 配列要素からヒープを作成するには、make_heapを使用します。
  • 以下を k 回実行します。
    • 最初の要素を読み取ります。
    • pop_heapを使用してポップする

背後にあるアルゴリズムを知らなくても、 priority queueのメソッド ( c'tor、top、pop ) を使用して同じことを達成できます。

複雑さ: O(n+ k * log(n)) 最悪の場合

于 2016-12-14T19:20:48.543 に答える