检查两个二维列表算法的重复？

Question

给出了

两个List>（称为a和b）。

它返回：地图，列表>>

• 设 a、b 的项为 a1、a2、a3、... 和 b1、b2、b3...
• 仅选择 b1 和 a1 的元素中字符串重叠的项目（List）
• 在结果中输入 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;
    }

Answer 1

我不确定是否有办法将其降低到

O(n^2)

以下，但为了将其降低到

O(n^2)

，我们可以将

List.contains

O(n)

降低到

HashMap.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

中对应的元素

    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);
    }