2

問題は次のとおりです。文字列のリストと整数 k が与えられた場合、頻度に基づいて降順で最も頻繁に出現する上位 k 個の単語を返します。これは O(N) である必要があります。ここで、N は文字列のリストの長さです。

一般的な解決策は、(単語、頻度) をハッシュ テーブルに格納し、ハッシュ テーブルを頻度で並べ替え、上位 k 単語を出力することです。ただし、頻度によるソートには O(NlgN) かかるため、これは O(N) ではありません。

O(N) ソリューションが実際に存在するかどうか疑問に思っています。k 番目に出現頻度の高い単語を取得し、残りの頻度を並べ替える場所をクイック選択することを考えましたが、それは O(N + klgk) であり、k が N の場合でも O(NlgN) です。

4

2 に答える 2

1

はい、存在します。実際にペアをソートする必要はありません。O(n) で k 番目の要素を見つけることができます (これはよく知られたアルゴリズムです)。次に、k 番目の要素以上のすべての要素が最上位の要素になります。

于 2014-08-09T17:03:32.023 に答える
1

はい、O(n) ソリューションがあります。

O(n) の複雑さで実行される有名な SELECT アルゴリズムを必要に応じて変更できます (アルゴリズムの目的は、N 個の要素から K 番目に小さい要素を見つけることです)。

その後、アルゴリズムが返す要素と「以上」の要素を選択するだけです。

詳細については、SELECT アルゴリズムを参照してください。

于 2014-08-09T19:08:18.387 に答える