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

Hot Tools

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft

PhpStorm Mac version

PhpStorm Mac version

The latest (2018.2.1) professional PHP integrated development tool

DVWA

DVWA

Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function