如何设计算法，该算法可以在O（n）时间中返回文档中的10个最常用的单词？如果可以使用其他空间。
我可以用计数解析并将单词放在哈希地图中。但是接下来，我必须对值进行排序以获取最常见的值。另外，我必须有一个映射btw的值 ->键，由于值可能会重复。
。那么我该如何解决？
这是一个简单的算法：
- 一次通过文档阅读一个单词。 O（n）
- 使用每个单词构建一个标签。 O（n）
- 使用该单词作为密钥。 O（1）
- 使用您将此词视为值的次数。 O（1）
- （例如。如果您将密钥添加到hashtable中，则值为1；如果您已经在空语中具有键，请将其关联的值增加1） o（1）
- 创建一对尺寸10的阵列（即字符串单词[10]/int count [10]或使用A＆lt; Pair>），使用此对来跟踪10个最常见的单词，他们的单词计数在下一步。 O（1）
- 遍历完整的Hashtable： o（n）
- 如果当前单词的字数比数组对中的条目更高，请替换该特定条目并将所有内容移动1个插槽。 O（1）
- 输出一对阵列。 O（1）
o（n）运行时。
o（n） hashtable arrays的存储
（旁注：您只能将空语视为词典：存储密钥的一种方式：键唯一的值对。从技术上讲，哈希图暗示着异步访问，并且可介绍可介绍。）
如果使用正确的数据结构，则可以在O（n）中完成。
考虑一个Node，由2件事组成：
- 一个计数器（最初设置为0）。
- 255（或任何数量字符）指针的数组为
Node。所有指针最初都设置为NULL。
创建一个根节点。定义"当前" Node指针，将其设置为最初的根节点。然后浏览文档的所有字符并执行以下操作：
- 如果下一个字符不是空间 - 从当前节点的数组中选择适当的指针。如果是
NULL-分配它。当前的Node指针已更新。 - 如果是一个空间（或任何单词定界符） - 递增"当前"
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
最快的方法是使用radix树。您可以将单词计数存储在Radix树的叶子上。保留10个最常见单词的单独列表及其出现计数以及一个存储进入此列表所需的阈值值的变量。在将项目添加到树上时更新此列表。
我将使用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;
运行时间应为o（n），以构建标签和arraylist。将前10个列表列入O（m），其中m是唯一单词的数量。o（n m）其中n>> m-> o（n）
维护（word，count）的地图为o（n）。
构建地图后，迭代键并检索十个最常见的键。
o（n） o（n）
- 但对所需的额外外部内存量的Soln COZ并不完全满意。