4

今天参加了一家公司的笔试。整个测试集中在数据结构上。我遇到了一个我认为我解决了的问题。但是我在计算数据结构的大 O 函数时遇到了困难。我将提供我想出的问题和答案。

给定您需要存储的文档和文档中的单词，并且应该能够在输入任何单词时返回计数。为您提供char* GetNextWord().

  1. 你会选择什么数据结构
  2. 给出算法
  3. 你的算法的顺序是什么

对于问题 1，我写了我会选择 TRIE 数据结构。对于问题 2，我给出了一个简短的算法。我写道，我将构建 TRIE 数据结构如下。

struct TRIE{
 boolean isWord;
 int count;
 Node* myList;
}

struct Node{
 char* character;
 Node *next;
 TRIE *child;
}

我有方法可以为每个单词constructTrie()做一个。addToTrie()

我写的顺序addToTrie()是 O( k )，其中k是长度。的顺序constructTrie()是N *O( k )，其中N是单词的数量。

现在我的问题是：我提到的命令是否正确？如果没有，将来如何解决这样的问题（给定一个 ds 查找命令）。使用 O( k )后我真的很困惑。它让我假设 O(1)。

提示/提示/建议是敞开的！

编辑：更正了清楚地提到应该为所有唯一单词存储字数的问题。

4

2 回答 2

2

比较两个通用字符串需要 Θ(k) (k = min strlen)，你必须查看的单词数是 N，所以 Ω(Nk) 应该是你能得到的最有效的复杂度。

于 2010-02-27T07:47:16.947 回答
1

如果您真的想使用 trie，那么addToTrie()确实是O(k)，其中 k 是您要添加的单词的长度。如果您只调用每个单词，constructTrie()将采用O(Nk)其中N是单词数。addToTrie()但是，您不需要addToTrie()为每个单词调用该函数。完成添加单词后，只需将 trie 指针重置到 trie 的根，然后在移动当前单词时移动指针，同时添加字符。伪代码：

trieNode *curr = trieRoot;
for each character c in document
  if it's a word terminator (space etc)
    add a character at curr signaling the end of the current word ('\0' maybe);
    curr = trieRoot;
  else if character is not a separator
    add character c at curr->next->character[c];
    curr = curr->next;

这将为您提供构建 trie 的O(C)运行时间，其中C是文档中的字符数。

现在，这引出了一个问题：你为什么需要 trie？显然，您找到了一种检测单词何时结束的方法，那么为什么必须将单词添加到 trie 中呢？太矫枉过正了。您需要的唯一数据结构是一些变量：一个用于跟踪当前字符，一个用于跟踪前一个字符，一个用于计算单词。这很容易在O(C)中完成，如下所示：

char prev = '\0';
char curr;
int count = 0;

for each character curr
  if curr is a word separator and prev isn't 
    ++count;
  prev = curr;

我认为对这个问题使用 trie 是没有意义的，它只会使事情复杂化。我认为，如果他们想测试您对尝试的了解，他们会给您一个尝试更有意义的问题。

即使他们给了你一个getNextWord()函数（你必须使用它吗？因为没有它你可以做得更好），我猜它会在没有更多单词时返回“\0”或其他东西？那么为什么你不能在它返回“\0”之前调用它并计算这样的单词呢？无论哪种方式，trie 在这里都没有意义。

于 2010-02-27T08:51:20.777 回答