我有一个二维字母数组,每个字母都有一个分数。例如:
J-95 O-90 H-92 N-99
I-91 0-89 L-55
1-80
T-55
从上面的数组中,我想快速获得前 20 个左右排列(按分数)的列表。在上面的示例中,列表将是:
JOHN
IOHN
J0HN
I0HN
... etc
我目前正在递归函数中执行此操作——但它比我希望的要慢。有什么好的方法可以快速得到top N list吗?我的代码是 C++(如果有好的库建议)。
谢谢
编辑:
我结合使用 Sneftel 和 Ethan 的答案解决了这个问题。我使用修剪函数根据权重减少可能的字符,然后从中计算排列。
最佳答案
首先,您需要对候选人进行排序。它需要 O(nlgn) 时间。
N-99 J-95 H-92 I-91 O-90 0-89 1-80 L-55 T-55
其次,根据您需要多少个最佳分数,您选择前 n 个字符进行排列。
(n)*(n-1)*(n-2)*(n-3) / (1 * 2 * 3 * 4) >= m.
n 是您选择的候选人数。 m 是您需要的最佳分数的数量。例如,如果您需要 20 个最佳分数,则只需设置 7 个字符。您面临的问题可能是您对所有候选人进行排列,而对一些非常低的候选人进行排列是一种浪费。
第三步是得到你需要的所有排列,然后排序并打印。
关于c++ - 如何有效地计算顶部排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21871536/