優化的方式來檢查對象的價值之間的平等列表

裏面我有兩個列表：
答：列表<MyCustomObject>
B.列出<MyCustomObject>優化的方式來檢查對象的價值之間的平等列表

MyCustomObject有各個領域。例如，一個場ID

在我的計劃，我需要檢查，如果同一ID兩個列表中存在。所以，目前我做嵌套迭代：

for(int i=0;i<a.size();i++) { 

    MyCustomObject obj = a.get(i); 

    for(int j=0;j<b.size();j++) { 

    if(obj.getId().equals(b.get(j).getId()) { 

     //do something 
     break; 
     } 
    } 
}

正如我經常需要做這個手術，看起來我沒有優化的，因爲我經常遍歷一長串。

如何優化此操作？

來源

2014-02-07 Novice User

難道你不能以'id'作爲關鍵字在'Map'中保存你的對象嗎？ – beny23

它不能小於'O（n^2）'。所以我認爲它非常好。你可以使用一些內置函數，但仍然是一樣的。儘管這種類型的問題需要在http://codereview.stackexchange.com/中提出。 –

@tintinmj確定它可以在小於'O（n^2）'的情況下完成！將第一個列表ID插入「HashSet」後跟隨第二個列表中每個ID的「m * O（1）」搜索的「O（n）」將給出實際上仍是線性時間搜索的內容。 – Alnitak

而不是使用一個列表，你可以使用一個Map，例如一個HashMap的 - 假設你的ID是一個int，它可能看起來像：

Map<Integer, MyCustomObject> objects = new HashMap<>(); 
//populate 
objects.put(someCustomObject.getId(), someCustomObject); 
//find an id: 
CustomObject obj = objects.get(someId);

注意：假設ID是唯一的。

來源

2014-02-07 19:18:06 assylias

線性時間算法是將第一個列表中的ID值與布爾值進行哈希運算。然後，您在第二個列表中查找ID值，並且如果散列已包含該ID的密鑰，則在兩個列表之間共享該ID。

您還可以通過對列表進行排序來改進O（n^2）的運行時間，這是一個O（n log n）操作，並且通過列表線性傳播以查看是否有任何值共享。如果要保留列表的順序，可以創建列表的另一個已排序副本，但會增加內存空間。

我相信，在不改變列表元素的順序或創建新的數據結構的情況下，您可以做得很好。不過，我不知道你的要求。

來源

2014-02-07 19:21:50

優化的方式來檢查對象的價值之間的平等列表

回答

相關問題