Auf Duplikate zweier 2D-Listenalgorithmen prüfen?

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

Das obige ist der detaillierte Inhalt vonAuf Duplikate zweier 2D-Listenalgorithmen prüfen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!