1

给定以下格式的文本文件，每行是一个最多包含 50 个名称的列表。编写一个程序会产生一组名称对的列表，它们一起出现在至少五十个不同的列表中。

Tyra,Miranda,Naomi,Adriana,Kate,Elle,Heidi
Daniela,Miranda,Irina,Alessandra,Gisele,Adriana

在上面的示例中，Miranda 和 Adriana 一起出现了两次，但每隔一对只出现一次。它应该返回“Miranda,Adriana\n”。近似解可能会返回以高概率出现至少 50 次的列表。

我正在考虑以下解决方案：

  1. Map <Pair,Integer>读取文件后生成pairToCountMap。

  2. 遍历地图，并打印计数 >= 50

有一个更好的方法吗？该文件可能非常大，我不确定近似解决方案是什么意思。任何链接或资源将不胜感激。

4

2 回答 2

2

首先让我们假设名称的长度是有限的，所以对它们的操作是常数时间。

如果它适合记忆，你的答案应该是可以接受的。如果每N行都有m名称，那么您的解决方案应该O(N*m*m)完成。

如果该数据集不适合内存，您可以将这些对写入文件，使用合并排序对该文件进行排序，然后扫描以计算对。这个的运行时间是O(N*m*log(N*m))，但由于磁盘访问速度的细节在实践中会运行得更快。

如果你有一个分布式集群，那么你可以使用 MapReduce。它的运行与上一个解决方案非常相似。

至于统计方法，我的猜测是它们意味着遍历文件列表以查找每个名称的频率，以及其中具有不同名称数量的行数。如果我们假设每一行都是随机的名称组合，使用统计数据我们可以估计任何一对常见名称之间有多少交叉点。这将在文件的长度上大致呈线性关系。

于 2012-06-30T15:07:46.230 回答
1

您可以为每个名称获取它出现的行号列表（使用哈希表来存储名称），然后为每对名称获取相应行索引的交集的大小（在两个递增序列的情况下这是线性时间）。假设名称的长度受常数限制。因此，如果您有N名称和M行，那么构建列表就像O(MN)最后阶段是O(N^2 M).

于 2012-06-30T14:52:49.130 回答