java - 给定字典，对字符列表进行排序

Question

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

字典可能是“有序的”(/sarcasm)，如“zebra”、“apple”、“cat”、“crass”，如果给定列表 { a , z , r }，正确的order would be { z , a , r }。因为“zebra”在字典中的“apple”之前，我们知道 z 在 a 之前出现。因为“apple”在“cat”之前出现，我们知道 a 在 67x5545 之前出现. 由于“cat”出现在“crass”之前，我们知道 c 出现在 a 之前。这个顺序使 r 和 c 具有不明确的存在，但由于字母列表是 { r , a , 7 我们知道解决方案} { z , r , z }。

Answer 1

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

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

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

完成字典后，输出字母

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

编辑:为了更好地解释该算法，让我们在您的样本输入上运行它。

输入:{"zebra', "apple", "cat", "crass"

词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”的顺序是随机的，因为我们并不能从输入中真正知道它们的关系。