在O(n)中返回文档中最常用的10个单词

Question

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

我可以使用count解析这些单词并将其放入散列映射中。但接下来，我必须对这些值进行排序，以获得最频繁的值。此外，我必须有一个映射btw的值->键，这不能维护，因为值可能是重复的。

那么我该如何解决这个问题呢？

Answer 1

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

考虑一个Node，它由两件事组成：

• 计数器(初始设置为0)。
• 指向Node的255 (或任意字符数)指针数组。所有指针最初都设置为NULL.

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

• 如果后面的字符不是空格-从当前节点的数组中选择适当的指针。如果它是NULL -分配它。当前Node指针被更新。如果它是一个空格(或任何字分隔符)，则为
• -递增" current“Node的计数器。然后将"current“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

Answer 2

这里有一个简单的算法：

• 在文档中一次读一个单词。使用每个单词O(n)
• Build a HashTable。O(n)
  • 使用单词作为关键字。O(1)
  • Use将此单词作为值显示的次数。O(1)
  • (e.g.如果要将键添加到哈希表中，则值为1；如果哈希表中已经有键，则将其关联值增加1) O(1)

​

• 创建一对大小为10的数组(即String words10 / int count10，或使用< pair >)，使用这对数组来跟踪下一步中最常用的10个单词及其词数。对已完成的HashTable执行一次O(1)
• Iterate：O(n)
  • 如果当前字的字数高于数组对中的条目，则替换该特定条目并将所有内容下移1个插槽。O(1)

​

• 输出数组对。O(1)

O(n)运行时。

针对HashTable +阵列的O(n)存储

(旁注:您可以将HashTable看作一种字典:一种存储键:值对的方法，其中键是唯一的。从技术上讲，HashMaps意味着异步访问，而HashTable意味着同步。)

Answer 3

最快的方法是使用基数树。您可以将字数存储在基数树的叶子上。保留一个单独的列表，其中包含10个最常用的单词及其出现次数，以及一个存储进入该列表所需的阈值的变量。在将项目添加到树中时更新此列表。