檢查兩個二維列表演算法的重複？

php小編百草帶來了一場關於Java演算法的精彩問答：如何檢查兩個二維列表中的重複元素？這是許多Java程式設計師在日常開發中經常遇到的問題之一。透過本文的討論和解析，讀者將能夠了解不同的解決方案和最佳化策略，從而更好地理解和掌握Java程式設計中處理類似問題的方法和技巧。

問題內容

給兩個list>（簡稱a和b）。

它回傳：map，list>>

• 設 a、b 的項為 a1、a2、a3、... 和 b1、b2、b3...
• 只選擇 b1 和 a1 元素中字串重疊的項目（list）
• 在結果中輸入鍵 = b1、值 = a1。

例如)

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

實際上，a和b中的列表長度至少會超過100,000。 我使用 list.contains 嘗試了這種方法，但最壞情況下時間複雜度為 o(n^3)。

這是我的程式碼，我想將該演算法的時間複雜度降低到 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;
    }

解決方法

我不確定是否有辦法將其減少到o(n^2) 以下，但為了將其減少到o( n^2)，我們可以透過hashmap 來減少<code>list.contains o(n) .get，即o(1) 時間複雜度。

建議不要檢查contains，而是尋找清單a 中元素的索引，b 元素將取得該索引並取得a 對應的列表。

首先，建立一個 map，其中包含 a 的元素作為鍵，值作為索引。

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

這是 ainset 的輸出，現在我們有了所屬元素的索引清單。

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

然後我們將 b 中元素列表的索引組合起來，得到 a 中對應的元素。

例如，對於 [a, d]，我們有一個組合集合 [0, 1, 2]。這是程式碼

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

以上是檢查兩個二維列表演算法的重複？的詳細內容。更多資訊請關注PHP中文網其他相關文章！