Menyemak pertindihan dua algoritma senarai 2D?

Editor PHP Baicao membawakan Soal Jawab yang menarik tentang algoritma Java: Bagaimana untuk menyemak elemen pendua dalam dua senarai dua dimensi? Ini adalah salah satu masalah yang sering dihadapi oleh banyak pengaturcara Java dalam pembangunan harian. Melalui perbincangan dan analisis artikel ini, pembaca akan dapat mempelajari tentang penyelesaian yang berbeza dan strategi pengoptimuman, supaya lebih memahami dan menguasai kaedah dan teknik untuk menangani masalah serupa dalam pengaturcaraan Java.

Kandungan soalan

Diberi dua senarai74ee2407650e54d8a2f7ea922e30be6b> (dirujuk sebagai a dan b).

Ia kembali: peta74ee2407650e54d8a2f7ea922e30be6b, senarai74ee2407650e54d8a2f7ea922e30be6b>>

• Andaikan sebutan a dan b ialah a1, a2, a3,... dan b1, b2, b3...
• Pilih item sahaja dengan rentetan bertindih dalam elemen b1 dan a1 (senaraie16aab792c943d9fbb1e2df2ac188ec2)
• Masukkan kunci = b1, nilai = a1 dalam keputusan.

Sebagai contoh)

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

Malah, panjang senarai dalam a dan b akan sekurang-kurangnya melebihi 100,000. Saya mencuba pendekatan ini menggunakan list.contains tetapi kerumitan masa kes terburuk ialah o(n^3).

Inilah kod saya, saya ingin mengurangkan kerumitan masa algoritma ini ke bawah 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;
    }

Penyelesaian

Saya tidak pasti sama ada ada cara untuk mengurangkan ini kepada o(n^2) 以下，但为了将其减少到 o(n^2)，我们可以通过 hashmap 减少 <code>list.contains o(n) .get，即 o(1) kerumitan masa.

Adalah disyorkan untuk tidak menyemak contains，而是查找列表 a 中元素的索引，b 元素将获取该索引并获取 a senarai yang sepadan.

Pertama, bina elemen map，其中包含 a sebagai kunci dan nilai sebagai indeks.

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

Ini ialah output ainset, kini kami mempunyai senarai indeks bagi elemen yang dimilikinya.

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

Kemudian kita akan b 中元素列表的索引组合起来，得到 a elemen yang sepadan.

Sebagai contoh, untuk [a, d]，我们有一个组合集 [0, 1, 2]. Inilah kodnya

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

Atas ialah kandungan terperinci Menyemak pertindihan dua algoritma senarai 2D?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!