给定一个字典，按顺序排列字符列表

Question

给定一个字典，按顺序排列字符列表

3

在面试中我被问到了这个问题。假设你有一个有序字典，并且给定一个无序的字符列表，你会如何按照优先级排序这些字符？该字典包含单词，其中保证出现了所有的26个字符。然而，请注意字典的大小可能是任意的。字典可能很小，可能没有为每个字符单独的部分，例如可能没有以a开头的单词部分；尽管a将出现在另一个单词中，例如“bat”。

该字典可能"有序"（/讽刺）地排列为"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}。

- OckhamsRazor

1

给定一个包含一些共享前缀的单词的字典，可能可以推导出正确的顺序（例如 "cat", "car" 可以看出 t < r）。但是在给定的例子中并非如此；我无法看出他们从哪里得到了 'r' 的顺序。 - Emil Vikström

@Emil 谢谢。我已经更新了示例，也许现在更有意义了。无论如何，我承认这是一个非常奇怪的问题。 - OckhamsRazor

3

我没有解决方案，但我有一个想法：从字典中列出已知的优先规则列表。在给定的例子中，它们将是 z<a, z<c, a<c, a<r。可选地，添加 z<r 因为优先级是传递的。通过假设 "X<Y" 等同于 "节点 X 与节点 Y 之间有单向连接"，将规则转换为有向无环图。找到一条遍历所有你想排序的字符的路径。该路径上的节点即为所需排序顺序。 - Kevin

在您的问题陈述中，您应该包括一个测试用例，其中一个字母不是以字符开头，并展示它是如何处理的。 - kasavbere

@Mooing Duck，如果第一个单词是“zer”而不是“zebra”，那么“r”会在哪里？ - kasavbere

显示剩余4条评论

3个回答

1

从“斑马”<“苹果”<“猫”<“粗鲁”的事实来看，推导每个字符之间的关系最有效的方法是循环考虑所有单词的第N个字符，其中N最初为0，得出关系“z”<“a”<“c”。该循环可以递归地提取具有相同前缀（即位置<= N的文本）的单词组的（N + 1）th字符的关系。对于具有相同前缀的“猫”和“粗鲁”的N == 1，这样做会产生关系“a”<“r”。

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

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

暴力方法是在输入列表中迭代所有字符对（即{a，z，r} -> az，ar，zr），查找表格以获取a<z，a<r，z<r：如果这个条件不成立，则交换字符并重新开始整个过程。当您完成整个过程而无需交换任何更多的字符时，输出将根据规则一致排序。这有点像进行冒泡排序。

为了使其更快，我们可以更积极地填充我们的表格中的单元格以表示隐含关系：例如，我们知道“z”<“a”<“c”和“a”<“r”，因此我们推断出“z”<“r”。我们可以通过运行上面的“naive”表格来查找我们了解每个字符的所有信息（例如，z<a和z<c）-然后运行我们所知道的关于a和c的内容。为避免过度深入的树，您可以只跟随这样的一级间接引用，然后重复直到表格稳定。

- Tony Delroy

这与Jingteng Xue的答案非常相似，除了他展示了一种从网格中按顺序提取字母的快速方法，即通过找到所有Y的行，然后删除该行/列。（假设删除行/列很快） - Mooing Duck

@Mooing Duck：并不是说任何列或行都会被完全指定...可能存在无法链接的不同部分排序。 - Tony Delroy

-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是字典中字符的数量，即一个特定的字母仅出现一次且是您检查的最后一个字符。

- kasavbere

这个示例是正确的。基本上，字典已经按照不是ABCDEF...的字母顺序进行了排序，我们需要找出字母的顺序。 - Mooing Duck

它并不按照 ABCDEF 的顺序排列是显而易见的。在您的问题陈述中，您应该包括一个测试用例，其中一个字母不是单词开头，并展示如何处理它。 - kasavbere

@Mooing Duck，你太快就点了反对按钮，然而你的回复并没有任何意义。难道你的意思不是“apple”在“crass”之前吗？ - kasavbere

抱歉，我的评论确实毫无意义。在他的示例中，a之所以出现在r之前，是因为“cat”出现在“crass”之前。 - Mooing Duck

恕我直言，我不同意我是错误的说法。我感觉我完全理解了这个问题。在他的示例字典中，“cat”排在“crass”之前，因此我们知道在我们正在查找的排序/字母表中，a比r具有更高的优先级。虽然我承认第一次阅读时感到困惑。 - Mooing Duck

显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- HelloWorld · Accepted Answer

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

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

其次，逐个单词扫描输入字典，并将每个单词与前一个单词进行比较。您应该为您扫描的每个单词找到确切的关系。因此，在这张图中添加一条边。假设字典是正确的，则不应出现冲突。

完成字典后，按以下方式输出字母表：

随机选择一个顶点，遍历其路径，直到找到指向 nothing 的一个字符。这是字母表中的第一个字符。输出它并将其从图中删除。
重复执行步骤 1 直到所有顶点都被删除。

编辑：为了更好地解释这个算法，让我们以您的样本输入作为例子运行它。

输入：{"zebra', "apple", "cat", "crass"}

单词0和单词1，我们立即知道z在a之前，所以我们建立一条边a->z

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

单词2和单词3，第一个字母相同为"c"，但第二个字母不同，所以我们得到a在r之前，因此我们有另一条边r->a

现在所有单词都被读取。通过随机选择一个顶点（假设我们选择了c），然后我们可以在图中找到c->a->z的路径。输出z并将其从图中删除（标记为NULL）。现在选择另一个顶点（假设我们选择了r），然后我们发现图中有r->a的边。我们输出a并将其从图中删除。现在我们再次选择c，没有找到路径，所以我们只需输出c并将其删除。最后选择r，再次没有找到路径，所以我们输出r并将其删除。由于所有顶点都已删除，该算法完成。

输出为z，a，c，r。 "c" 和 "r" 的顺序是随机的，因为我们从输入中不知道它们之间的关系。