4

如何设计一种算法，可以在 O(n) 时间内返回文档中最常用的 10 个单词？如果可以使用额外的空间。

我可以使用 count 解析单词并将其放置在哈希图中。但接下来我必须对值进行排序以获得最常见的值。此外，我必须有一个映射 btw 值 -> 键，因为值可能重复，所以无法维护。

那么我该如何解决呢？

4

5 回答 5

5

这是一个简单的算法：

  • 通过文档一次阅读一个单词。在）
  • 使用每个单词构建一个 HashTable。在）
    • 用这个词作为关键。O(1)
    • 使用您看到这个词的次数作为值。O(1)
    • （例如，如果您将键添加到哈希表，则值为 1；如果您已经在哈希表中拥有键，则将其关联值增加 1）O(1)
  • 创建一对大小为10的数组（即String words[10] / int count[10]，或者使用<Pair>），在下一步中使用这对来跟踪10个最频繁的单词及其单词数. O(1)
  • 遍历完成的 HashTable 一次：O(n)
    • 如果当前单词的字数高于数组对中的条目，则替换该特定条目并将所有内容向下移动 1 个插槽。O(1)
  • 输出这对数组。O(1)

O(n)运行时间。

哈希表 + 数组的O(n)存储

（旁注：您可以将 HashTable 视为字典：一种存储键值对的方法，其中键是唯一的。从技术上讲，HashMap 意味着异步访问，而 HashTable 意味着同步。）

于 2012-10-25T21:44:57.057 回答
2

如果您使用正确的数据结构，它可以在 O(n) 中完成。

考虑 a Node，由两件事组成：

  • 一个计数器（最初设置为 0）。
  • 一个包含 255 个（或任意数量的字符）指针的数组Node。所有指针最初都设置为NULL.

创建一个根节点。定义一个“当前”Node指针，最初将其设置为根节点。然后遍历文档的所有字符并执行以下操作：

  • 如果下一个字符不是空格 - 从当前节点的数组中选择适当的指针。如果是NULL- 分配它。当前Node指针被更新。
  • 如果它是一个空格（或任何单词分隔符） - 增加 "current" 的计数器Node。然后重置“当前”Node指针以指向根节点。

通过这样，您可以在 O(n) 中构建一棵树。每个元素（节点和离开）都表示一个特定的单词，以及它的计数器。

然后遍历树以找到具有最大计数器的节点。它也是 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)。

构建地图后，遍历键并检索十个最常用的键。

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 回答