1

我一直在研究一个需要算法的实际情况，并从中提出了一个通用问题。考虑到有两个数组：-

源[10] = {'a', 'v', 'l', 'r', 'p', 's', 'x', 'd', 'q', 'o' , 'g', '我'}

目标[N] = {'a', 'v', 'l', 'r', 'p', 's', 'x', 'd', 'q', 'o' , 'g', 'm',a', 'v', 'l', 'r', 'p',a', 'v', 'l', 'r', 'p',a',

'v'，'l'，'r'，'p'，a'，'v'，'l'，'r'，'p'，a'，'v'，'l'，'r'， 'p',a', 'v', 'l', 'r', 'p',a', 'v', 'l', 'r', 'p',a', 'v',

'l', 'r', 'p',a', 'v', 'l', 'r', 'p', ....}

我们需要有一个有效的算法来找到来自 Source 中的字符在 Target 中的出现频率。

我曾想过散列完整的目标列表，然后遍历源并在散列列表中进行查找。人们可以评论/验证该方法吗？

4

2 回答 2

2

如果您的字符集受到合理限制，您可以使用字符代码作为计数数组的索引。假设您有 16 位字符。你可以这样做：

int[] counts = new int[65536];
foreach (char c in Target)
    counts[c]++;

有了手中的数组，您可以通过从数组中counts查找代码轻松找到频率。Sourcecounts

这个解决方案尽可能快地渐近，但它可能不是内存效率最高的解决方案。

于 2013-01-25T16:42:49.760 回答
0

我不知道哈希列表是什么，所以我不能对此发表评论。为了提高效率，我建议将目标数组转换为多集。Guava有一个很好的实现（尽管 Java Collections Framework 没有）。Apache Commons（称为 a ）也是如此Bag。然后，您可以简单地遍历源并查找多重集中每个元素的频率。如该线程中所述，使用多重集比使用HashMap从元素到频率更容易，尽管它确实需要使用第三方库。

于 2013-01-25T16:16:03.190 回答