2

我有两个列表列表，子列表代表路径。我想找到所有路径。

List<List<E>> pathList1
List<List<E>> pathList2

当然，天真的解决方案：

List<List<E>> result = new ArrayList<List<E>>();

for(List<E> p1 : pathList1) {
   for(List<E> p2: pathList2) {
      List<E> newList = new ArrayList<E>(p1.size()+p2.size());
      newList.addAll(p1);
      newList.addAll(p2);
      result.add(newList);
   }
}

不相关的理论问题

我最近了解了时间复杂度。所以这是一个自我检查，如果我是正确的，我希望有人可以评论。

让 N = num 个列表在 pathList1

让 M = pathList2 中的 num 个列表

设 X = pathList1 中路径的平均长度

设 Y = pathList2 中路径的平均长度

所以如果被问到“这个函数的复杂性是多少？” 我会给

〜O（NM（X + Y））

我想知道是否有更快的方法来做到这一点？

也许更好的数据结构？

同时做吗？

制造某种“未来”并返回它？（完全披露，我对期货一无所知）。

我对聪明的技巧和独特的解决方案持开放态度，或者纯粹是实用的。

谢谢。

4

2 回答 2

3

你可以看看番石榴 ，特别是Sets#cartesianProduct

即你可以做这样的事情：

Sets.cartesianProduct(ImmutableList.of(
       ImmutableSet.of(Sets.newHashSet(pathList1)),
       ImmutableSet.of(Sets.newHashSet(pathList2)))
于 2014-01-08T19:03:09.030 回答
0

我对你的目标到底是什么感到困惑。

如果您有以下路径列表“（A，B，C）（D，E）”和“（C，D）（A，B）”

那么您当前的代码将返回

"(A,B,C,C,D),(D,E,C,D),(A,B,C,A,B),(D,E,A,B)"

那是你要的吗？这不是所有的路径，而是所有路径的组合。

所有路径的列表将是

“（A，B，C）（D，E）（C，D）（A，B）”

这可以在简单的 O(N) 时间内执行。

同样使用 Big-O 表示法，我们通常不关心单个变量，只关心问题复杂性的整体规模。它通常纯粹写成单个变量 n 的函数，n 是元素的数量。

但是，如果您想将两个列表“相乘”，一个元素的每个元素对另一个，那么它将是 O(n^2) 并且实际上没有更快的方法。

于 2014-01-08T18:50:06.637 回答