php小编百草带来了一场关于java算法的精彩问答：如何检查两个二维列表中的重复元素？这是许多java程序员在日常开发中经常遇到的问题之一。通过本文的讨论和解析，读者将能够了解到不同的解决方案和优化策略，从而更好地理解和掌握java编程中处理类似问题的方法和技巧。
问题内容
给出两个list>（简称a和b）。
它返回：map，list
>>
- 设 a、b 的项为 a1、a2、a3、... 和 b1、b2、b3...
- 仅选择 b1 和 a1 元素中字符串重叠的项（list
） - 在结果中输入键 = b1、值 = 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;
}
解决方法
我不确定是否有办法将其减少到 o(n^2) 以下，但为了将其减少到 o(n^2)，我们可以通过 hashmap 减少 <code>list.contains o(n) .get，即 o(1) 时间复杂度。
建议不要检查 contains，而是查找列表 a 中元素的索引，b 元素将获取该索引并获取 a 对应的列表。
首先，构建一个 map，其中包含 a 的元素作为键，值作为索引。
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]
然后我们将 b 中元素列表的索引组合起来，得到 a 中对应的元素。
例如，对于 [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);
} 
