3

我在一次采访中被问到这个问题。假设你有一个有序的字典，并且给定了一个无序字符列表——你将如何按优先顺序排列这些字符？该词典包含保证出现所有 26 个字符的单词。但是，请注意字典的大小可能是任何值。字典可能只有几个单词，并且每个字符可能没有单独的部分，例如，以a;开头的单词可能没有部分。尽管a将作为另一个词的一部分出现，例如“bat”。

字典可能是“有序的”（/sarcasm），例如“zebra”、“apple”、“cat”、“crass”，如果给定列表 { a, z, r}，正确的顺序是 { z, a, r}. 由于字典中“zebra”在“apple”之前，所以我们知道z在之前a出现。由于“apple”在“cat”之前，我们知道a在之前c。因为“cat”在“crass”之前，我们知道出现a在 之前r。这个排序离开c并且r存在不确定性，但是由于字母列表是 { a, z, r}，我们知道解决方案是 { z, a, r}。

4

3 回答 3

11

使用有 26 个顶点的有向图，每个顶点代表一个字符。从顶点 A 到顶点 B 的边意味着在字母表中 B 在 A 前面。

第一步是建立这样一个只有顶点但没有边的图。

其次，您逐字扫描输入字典。并将每个单词与前一个单词进行比较。您应该为您扫描的每个单词找到一个确切的关​​系。所以你在这个图中添加了一条边。假设字典是正确的，应该没有冲突。

完成字典后，您通过以下方式输出字母表

  1. 选择一个随机顶点，遍历它的路径，直到找到一个不指向任何东西的字符。这是字母表中的第一个字符。输出它并从图中删除它。
  2. 继续执行 1 直到所有顶点都被删除。

编辑：为了更好地解释这个算法，让我们在你的样本输入上运行它。

输入：{“斑马”、“苹果”、“猫”、“粗鲁”}

单词 0 和单词 1，我们马上就知道 z 在 a 之前，所以我们做一条边 a->z

单词 1 和单词 2，我们立即知道 a 在 c 之前，所以我们再做一条边 c->a

Word 2 和 Word 3，第一个字母是相同的“c”，但第二个字母不同，所以我们知道 a 在 r 之前，所以我们有另一个边 r->a

现在所有的单词都读完了。通过随机选择一个顶点来输出顺序（比如我们选择 c），然后我们在图中有 c->a->z。输出 z 并从图中删除 z（将其标记为 NULL）。现在选择另一个（假设我们选择 r），然后我们在图中找到 r->a。我们输出 a 并从图中删除 a。现在我们选择另一个（假设我们再次选择 c），没有找到路径，所以我们只输出 c 并删除它。现在我们选择最后一个，r，又没有路径了，所以我们输出r并删除它。由于删除了所有顶点，因此算法完成。

输出为 z、a、c、r。“c”和“r”的顺序是随机的，因为我们从输入中并不真正知道它们的关系。

于 2012-04-24T20:45:22.900 回答
1

从“zebra”<“apple”<“cat”<“crass”的事实来看，导出每个字符关系的最有效方法是让一个循环考虑所有单词的第 N 个字符，其中 N 最初为 0，产生关系“z”<“a”<“c”。该循环可以递归地提取具有相同前缀的单词组的第（N + 1）个字符的关系（即位置<= N的文本）。这样做是为了N == 1 具有相同前缀的“cat”和“crass”产生关系“a”<“r”。

我们可以在二维x < y真值数组中表示已知关系。

y\x a b c...r...z
a   -   N   N   Y
b     -
c   Y   -       Y
r   Y       -
z   N   N       -

The brute force approach is to iterate over all pairs of characters in the input list (i.e. {a, z, r} -> az, ar, zr) looking up the table for a<z, a<r, z<r: if this is ever false, then swap the characters and restart the whole she-bang. When you make it through the full process without having had to swap any more characters, the output is sorted consistently with the rules. This is a bit like doing a bubble sort.

为了加快速度，我们可以更主动地在表格中填充隐含关系的单元格：例如，我们知道“z”<“a”<“c”和“a”<“r”，所以我们推断“ z" < "r"。我们可以通过遍历上面的“naive”表来找到我们所知道的关于每个字符的所有信息（例如那个z<a和z<c）——然后遍历我们对 a 和 c 的了解。为避免树过深，您可以像这样只遵循一级间接，然后重复直到表稳定。

于 2012-04-25T08:44:00.410 回答
-3

根据您描述问题的方式，您的示例不正确。你的答案应该是{z,r,a}。然而，这可能是，下面是解决问题的代码。您可以修改它以返回与我设想的不同的订单{z,r,a}。

Set<Character> charPrecedence(List<String> dictionary, char[] letters){
    Set<Character> result = new HashSet<Character>();
    //since your characters are the 26 letters instead of the 256 chars
    // a bit vector won't do; you need a map or set
    Set<Character> alphabets = new HashSet<Character>();
    for(char c: letters)
       alphabets.add(c);

    //now get to work
    for(String word: dictionary){
       if(alphabets.isEmpty()) return result;
       for(char c: word.toCharArray()){
          if(alphabets.remove(c))
           result.add(c);
       }
    }
    //since the dictionary is guaranteed to contain all the 26 letters,
    //per the problem statement, then at this point your work is done.
    return result;
}

最佳情况 O(1); 最坏情况 O(n) 其中 n 是字典中的字符数，即一个特定字母只出现一次，并且是您检查的最后一个字符。

于 2012-04-24T23:15:16.360 回答