1

我有一个 ArraysList 包含M已排序的列表。Arraylist 中的每个列表都具有相同的大小N。现在我想将(N-1) 每个列表中的第一个对应值与其他值进行比较，并且我想找到具有相同第一个(N-1)值的那些列表。直观地说，它可以通过两个 for 循环来完成，但复杂度可能高达M*N*N. 我想知道是否有更好的算法来做到这一点。顺便说一句，M可能是一个非常大的数字，而N往往是一个较小的数字。

对不起，我可能不太清楚。我希望最终输出是具有相同第一个(N-1)值的列表对。

4

2 回答 2

3

使用良好的散列算法计算N-1每一行中项目的散列码。按哈希码组织行，仅当哈希码匹配时才进行完整比较。

于 2012-09-10T01:47:15.050 回答
0

对列表列表进行排序。

对它们进行排序O(N M LOG M)（假设比较是O(N)）。

如果您在基数排序方法中执行此操作，它实际上应该更多在行O(N * M)甚至O(M LOG M) 总计上（假设列表不相同）。

然后具有相同前缀的列表必须在此列表中的后续。

假设您正在尝试重新实现 APRIORI：是的，请保留候选项目集的排序列表。这正是 Apriori-Gen 构建下一轮候选者所需要的。将它们组织为排序树非常整洁，因为这在扫描数据库以计数项集时也很快。

于 2012-09-14T13:35:32.693 回答