Vérification de la duplication de deux algorithmes de liste 2D ?

L'éditeur PHP Baicao a apporté une merveilleuse séance de questions-réponses sur les algorithmes Java : Comment vérifier les éléments en double dans deux listes bidimensionnelles ? C'est l'un des problèmes que de nombreux programmeurs Java rencontrent souvent dans leur développement quotidien. Grâce à la discussion et à l'analyse de cet article, les lecteurs pourront découvrir différentes solutions et stratégies d'optimisation, afin de mieux comprendre et maîtriser les méthodes et techniques permettant de traiter des problèmes similaires en programmation Java.

Contenu de la question

Étant donné deux listes> (appelées a et b).

Il renvoie : map, list>>

• Supposons que les termes de a et b soient a1, a2, a3,... et b1, b2, b3...
• Sélectionnez uniquement les éléments dont les chaînes se chevauchent dans les éléments b1 et a1 (list)
• Entrez la clé = b1, la valeur = a1 dans le résultat.

Par exemple)

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

En fait, la longueur des listes en a et b sera d'au moins supérieure à 100 000. J'ai essayé cette approche en utilisant list.contains mais le pire des cas de complexité temporelle était o(n^3).

Voici mon code, je souhaite réduire la complexité temporelle de cet algorithme en dessous de 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;
    }

Solution de contournement

Je ne sais pas s'il existe un moyen de réduire cela à o(n^2) 以下，但为了将其减少到 o(n^2)，我们可以通过 hashmap 减少 <code>list.contains o(n) .get，即 o(1) complexité temporelle.

Il est recommandé de ne pas consulter la contains，而是查找列表 a 中元素的索引，b 元素将获取该索引并获取 a liste correspondante.

Tout d'abord, construisez un élément map，其中包含 a comme clé et une valeur comme index.

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

C'est le résultat de ainset, nous avons maintenant une liste d'indices de l'élément auquel il appartient.

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

Ensuite, nous allons b 中元素列表的索引组合起来，得到 al'élément correspondant.

Par exemple, pour [a, d]，我们有一个组合集 [0, 1, 2]. Voici le 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);
    }

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!