search
HomeJavaChecking for duplication of two 2D list algorithms?

php editor Baicao brought a wonderful Q&A about Java algorithms: How to check duplicate elements in two two-dimensional lists? This is one of the problems that many Java programmers often encounter in daily development. Through the discussion and analysis of this article, readers will be able to learn about different solutions and optimization strategies, so as to better understand and master the methods and techniques for dealing with similar problems in Java programming.

Question content

Given two list> (referred to as a and b).

It returns: map, list>>

  • Suppose the items of a and b are a1, a2, a3,... and b1, b2, b3...
  • Select only items with overlapping strings in b1 and a1 elements (list)
  • Enter key = b1, value = a1 in the result.

For example)

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

In fact, the length of the lists in a and b will be at least more than 100,000. I tried this approach using list.contains but the worst case time complexity was o(n^3).

Here is my code, I want to reduce the time complexity of this algorithm to below 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;
    }

Workaround

I'm not sure if there is a way to reduce this to below o(n^2), but in order to reduce it to o( n^2), we can reduce list.contains<code> o(n) .get through hashmap, that is, o(1) time complexity.

It is recommended not to check contains, but to look for the index of the element in the list a, the b element will get that index and get the a corresponding list.

First, build a map containing elements of a as keys and values ​​as indexes.

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

This is the output of ainset, now we have the index list of the element it belongs to.

a=[0, 2], b=[0], c=[0], d=[1, 2], e=[1], f=[1, 2]

Then we combine the indexes of the element lists in b to get the corresponding elements in a.

For example, for [a, d], we have a combination set [0, 1, 2]. This is the code

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

The above is the detailed content of Checking for duplication of two 2D list algorithms?. For more information, please follow other related articles on the PHP Chinese website!

Statement
This article is reproduced at:stackoverflow. If there is any infringement, please contact admin@php.cn delete

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Best Graphic Settings
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. How to Fix Audio if You Can't Hear Anyone
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
WWE 2K25: How To Unlock Everything In MyRise
1 months agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools

SublimeText3 English version

SublimeText3 English version

Recommended: Win version, supports code prompts!

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.