检查两个二维列表算法的重复？-Java-PHP中文网

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

王林

发布： 2024-02-22 13:55:06

转载

724人浏览过

php小编百草带来了一场关于java算法的精彩问答：如何检查两个二维列表中的重复元素？这是许多java程序员在日常开发中经常遇到的问题之一。通过本文的讨论和解析，读者将能够了解到不同的解决方案和优化策略，从而更好地理解和掌握java编程中处理类似问题的方法和技巧。

问题内容

给出两个list<list<string>>（简称a和b）。

它返回：map<list<string>，list<list<string>>>

设 a、b 的项为 a1、a2、a3、... 和 b1、b2、b3...
仅选择 b1 和 a1 元素中字符串重叠的项（list<string>）
在结果中输入键 = 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 对应的列表。

降重鸟

要想效果好，就用降重鸟。AI改写智能降低AIGC率和重复率。

113

查看详情

首先，构建一个 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);
    }

登录后复制

以上就是检查两个二维列表算法的重复？的详细内容，更多请关注php中文网其它相关文章！