提问人：noen 提问时间：11/10/2023 最后编辑：noen 更新时间：11/11/2023 访问量：74
检查两个二维列表算法的重复？
check duplication of two 2-dimensional-list algorithm?
问：
给出了两个 List<List<string>>（称为 a 和 b）。
它返回：Map<List<string>， List<List<string>>>
- 让 A、B 的项目分别为 A1、A2、A3,...和 B1，B2，B3...
- 仅选择 b1 和 a1 元素之间字符串重叠的项目 （List<string>）
- 在结果中输入 key = b1，value = a1。
例如）
Define a and b as follows:
a = [a, b, c], [d, e, f], [a, d, f]
b = [a, d], [a], [c], [x]
it returns :
key value
[a,d] | [a,b,c],[d,e,f],[a,d,f]
[a] | [a,b,c],[a,d,f]
[c] | [a,b,c]
[x] | empty list
实际上，a 和 b 中列表的长度将至少超过 100,000。
我使用 List.contains 尝试了这种方法，但在最坏的情况下，时间复杂度为 O（n^3）。
这是我的代码，我想将该算法的时间复杂度降低到 O（n^2） 以下。
public Map<List<String>, List<List<String>>> compute(List<List<String>> a, List<List<String>> b) {
Map<List<String>, List<List<String>>> result = new HashMap<>();
for (List<String> elem : b) {
result.put(elem, a.stream().filter(e -> e.stream().anyMatch(elem::contains)).toList());
}
return result;
}
答：
1赞
phuongnq1995
11/11/2023
#1
我不确定有没有办法将其降低到以下，但要将其降低到我们可以降低时间复杂性。O(n^2)O(n^2)List.containsO(n)HashMap.getO(1)
建议不是检查，而是在列表中找到元素的索引，元素会得到该索引并得到相应的列表。containsaba
首先，构建一个包含作为键和值的元素作为其索引。Mapa
Map<String, Set<Integer>> aInSet = new HashMap<>();
for (int i = 0; i < a.size(); i++) {
for (String elem : a.get(i)) {
Set<Integer> elementSet = aInSet.getOrDefault(elem, new HashSet<>());
elementSet.add(i);
aInSet.put(elem, elementSet);
}
}
这是 的输出，现在我们有了所属元素的索引列表。aInSet
a=[0, 2], b=[0], c=[0], d=[1, 2], e=[1], f=[1, 2]
然后，我们将元素列表的索引组合在一起，得到相应的 in 。ba
例如，我们有一个组合集。代码如下[a, d][0, 1, 2]
Map<List<String>, List<List<String>>> result = new HashMap<>();
for (List<String> elem : b) {
Set<Integer> elemSet = new HashSet<>();
for (String elemB: elem) {
elemSet.addAll(aInSet.getOrDefault(elemB, new HashSet<>()));
}
List<List<String>> listContainElem = elemSet.stream()
.map(a::get)
.collect(Collectors.toList());
result.put(elem, listContainElem);
}
评论
a