搜尋
首頁Java檢查兩個二維列表演算法的重複?

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中文網其他相關文章!

陳述
本文轉載於:stackoverflow。如有侵權,請聯絡admin@php.cn刪除

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
2 週前By尊渡假赌尊渡假赌尊渡假赌
倉庫:如何復興隊友
4 週前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
4 週前By尊渡假赌尊渡假赌尊渡假赌

熱工具

MantisBT

MantisBT

Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中

SublimeText3 英文版

SublimeText3 英文版

推薦:為Win版本,支援程式碼提示!

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

將Eclipse與SAP NetWeaver應用伺服器整合。

Dreamweaver Mac版

Dreamweaver Mac版

視覺化網頁開發工具