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!

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

VSCode Windows 64-bit Download
A free and powerful IDE editor launched by Microsoft

PhpStorm Mac version
The latest (2018.2.1) professional PHP integrated development tool

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
Powerful PHP integrated development environment

EditPlus Chinese cracked version
Small size, syntax highlighting, does not support code prompt function
