インタビューで質問されました。インタビュアーは、特定の文書の次の単語を返す getNextWord() という関数が存在すると仮定するように私に言いました。私の仕事は、タスクを実装するためのデータ構造を設計し、すべての単語とその頻度のリストを構築するアルゴリズムを提供することでした。
C++ の背景を持つ私の答えは、multimapofを作成し、stringその中にすべての単語を挿入し、後で of を表示するcountことでした。ただし、後で、これをより一般的な方法で行うように言われました。ジェネリックとは、彼が私にライブラリ機能を使用させたくないという意味でした。また、マルチマップは 2-3 ツリー程度として内部的に実装されていると思います。そのため、マルチマップ ソリューションを汎用にするためには、2-3 ツリーもコーディングする必要があります。
トライは思いつきましたが、面接中にそれを実行することは私にとって問題外でした。それで、それを達成するためのより良い方法があるかどうか知りたかっただけですか？または、試行を使用してスムーズに実装する方法はありますか?
ここでは、ヒストグラムベースのアルゴリズムは効率的で汎用的です。アイデアは単純です。データからヒストグラムを作成します。ヒストグラムの一般的なインターフェースはMap<String,Integer>
ヒストグラムを維持しながら、( nextDoc() メソッドを使用して) ドキュメントを 1 回繰り返します。
このインターフェイスの最適な実装は、大きな O 表記に関して、おそらくtrieを使用し、各リーフ ノードに出現回数のカウンターを追加することです。
トライから実際の(word,number)ペアを取得することは、トライ上の単純な DFS によって行われます。
このソリューションでは、O(n * |S|)時間の計算量が |S| で示されます。文字列の平均サイズです。
各単語の挿入アルゴリズム:
新しい単語を追加するたびに、その単語が既に存在するかどうかを確認し、存在する場合はカウンターを増やし、存在しない場合はカウンター値 1 で単語を辞書に追加します。
すべての単語を格納するために、 Bツリー（または非常によく似たsmth）を実装しようとします。したがって、次の単語がすでにある場合は簡単に見つけることができ、ノード内の関連するカウンターを増やすことができます。または、新しいものを挿入するだけです。
その場合の時間計算量は次のようになります。O(nlogn)ここで、nはすべての単語がカウントさlognれ、そのような種類のツリーのBig-Ohです。
最も簡単な解決策は aa Trieだと思います。この場合、O(N) が指定されます (挿入とカウントの取得の両方)。すべてのノードの追加スペースにカウントを格納するだけです。
基本的に、ツリーの各ノードには、26 の可能な子への 26 のリンク (文字ごとに 1 つ) + 1 つのカウンター (現在のノードで終了する単語の場合) が含まれます。トライのグラフィック イメージのリンクを参照してください。