Checking 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 listdc4b5854fa094b5d08a57a86ff781edf> (referred to as a and b).

It returns: mapdc4b5854fa094b5d08a57a86ff781edf, listdc4b5854fa094b5d08a57a86ff781edf>>

• 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 (list98c455a79ddfebb79781bff588e7b37e)
• 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!