4

ドキュメントで最も頻繁に使用される 10 個の単語を O(n) 時間で返すことができるアルゴリズムを設計するにはどうすればよいですか? 追加のスペースを使用できる場合。

count を使用して単語を解析し、ハッシュ マップに配置できます。しかし次に、最も頻度の高い値を取得するために値を並べ替える必要があります。また、値が繰り返される可能性があるため、維持できない値->キー間のマッピングが必要です。

では、どうすればこれを解決できますか?

4

5 に答える 5

5

簡単なアルゴリズムは次のとおりです。

  • ドキュメントを一度に 1 単語ずつ読み上げます。の上）
  • 各単語を使用して HashTable を作成します。の上）
    • 単語をキーとして使用します。O(1)
    • この単語を見た回数を値として使用します。O(1)
    • (たとえば、ハッシュテーブルにキーを追加する場合、値は 1 です。ハッシュテーブルに既にキーがある場合は、関連付けられた値を 1 増やします) O(1)
  • サイズ 10 の配列のペア (つまり、String words[10] / int count[10]、または < Pair > を使用) を作成し、このペアを使用して、次のステップで最も頻繁に使用される 10 の単語とその単語数を追跡します。 . O(1)
  • 完成した HashTable を 1 回繰り返す: O(n)
    • 現在の単語の単語数が配列ペアのエントリよりも多い場合は、その特定のエントリを置き換えて、すべてを 1 スロット下にシフトします。O(1)
  • 配列のペアを出力します。O(1)

O(n)ランタイム。

HashTable + 配列のO(n)ストレージ

(補足: HashTable は辞書と考えることができます。つまり、キーが一意であるキーと値のペアを格納する方法です。技術的には、HashMap は非同期アクセスを意味し、HashTable は同期アクセスを意味します。)

于 2012-10-25T21:44:57.057 に答える
2

正しいデータ構造を使用すれば、O(n) で実行できます。

Node次の 2 つで構成される を考えてみましょう。

  • カウンター (最初は 0 に設定)。
  • への 255 (または任意の数の文字) ポインターの配列Node。すべてのポインターは、最初は に設定されていNULLます。

ルート ノードを作成します。「現在の」Nodeポインタを定義し、最初にルート ノードに設定します。次に、ドキュメントのすべての文字を調べて、次の操作を行います。

  • 次の文字がスペースでない場合、現在のノードの配列から適切なポインタを選択します。もしそうならNULL- それを割り当てます。現在のNodeポインターが更新されます。
  • スペース (または区切り文字) の場合 - "current" のカウンターをインクリメントしますNode。Node次に、ルート ノードを指すように「現在の」ポインタをリセットします。

このようにして、O(n) にツリーを構築します。すべての要素 (node と leave の両方) は、特定の単語とそのカウンターを表します。

次に、ツリーを横断して、最大のカウンターを持つノードを見つけます。ツリー内の要素の数が O(n) よりも大きくないため、これも O(n) です。

アップデート：

最後のステップは必須ではありません。実際、最も一般的な単語は、文字処理中に更新される場合があります。以下は疑似コードです。

struct Node
{
    size_t m_Counter;
    Node* m_ppNext[255];
    Node* m_pPrev;

    Node(Node* pPrev) :m_Counter(0)
    {
        m_pPrev = pPrev;
        memset(m_ppNext, 0, sizeof(m_ppNext));
    }
    ~Node()
    {
        for (int i = 0; i < _countof(m_ppNext) i++)
            if (m_ppNext[i])
                delete m_ppNext[i];
    }

};

Node root(NULL);
Node* pPos = &root;
Node* pBest = &root;
char c;

while (0 != (c = GetNextDocumentCharacter()))
{
    if (c == ' ')
    {
        if (pPos != &root)
        {
            pPos->m_Counter++;

            if (pBest->m_Counter < pPos->m_Counter)
                pBest = pPos;

            pPos = &root;
        }
    } else
    {
        Node*& pNext = pPos->m_ppNext[c - 1];
        if (!pNext)
            pNext = new Node(pPos);
        pPos = pNext;
    }
}

// pBest points to the most common word. Using pBest->m_pPrev we iterate in reverse order through its characters
于 2012-10-25T21:48:59.743 に答える
2

最も速いアプローチは、基数ツリーを使用することです。基数ツリーのリーフに単語数を格納できます。最も頻繁に使用される 10 の単語とその出現回数の別のリストを、このリストに入るために必要なしきい値を格納する変数と共に保持します。項目がツリーに追加されると、このリストを更新します。

于 2012-10-25T21:55:52.553 に答える
0

(word,count) のマップを維持すると O(n) になります。

マップが作成されたら、キーを反復処理して、最も一般的な 10 個のキーを取得します。

O(n) + O(n)

-- しかし、必要な外部メモリの量が増えるため、このソリューションにはまったく満足できません。

于 2012-10-25T21:45:11.993 に答える
0

ArrayList と HashTable を使用します。

これが私が考えているアルゴリズムです。

Loop through all the word in the document.

if (HashTable.contains(word) )
    increment count for that word in the HashTable;
else
    ArrayList.add(word);
    HashTable.add(word);
    word count in HashTable = 1;

ドキュメント全体をループした後、

Loop through ArrayList<word>
    Retrieve the word count for that word from the HashTable;
    Keep a list of the top 10 words;

HashTable と ArrayList を構築するための実行時間は O(n) である必要があります。上位 10 リストを作成するのは、O(m) である必要があります。ここで、m は固有の単語の数です。O(n+m) ただし、n>>m --> O(n)

于 2012-10-25T21:50:34.577 に答える