消除或避免加入重複在與ArrayList的自定義對象

我有一個自定義對象在該結構中消除或避免加入重複在與ArrayList的自定義對象

static class Node { 
    int col; 
    int row; 
    int g; 
    int h; 
    int f; 

    public Node(int col, int row, int g, int h) { 
     this.col = col; 
     this.row = row; 
     this.g = g; 
     this.h = h; 
     this.f = g+h; 
    } 
}

的col和row變量是唯一的，並且可以在ArrayList<Node> myList只出現一次。

有沒有一種方法來避免添加或檢查可能的重複，而不必做一個討厭的for-loop？

我知道Set接口可能是一個解決方案，因爲重複不會發生，但我現在有很多代碼，我不想重構，除非它變得有必要。

來源

2012-11-06 JavaCake

這裏是你的選擇。所有這些解決方案都需要正確實施equals和hashCode。既然你想row和col是唯一的：

public boolean equals(Object obj) { 
    if (obj == null || obj.getClass() != Node.class) { 
     return false; 
    } 
    Node other = (Node) obj; 
    if (other.col != this.col) { 
     return false; 
    } 
    if (other.row != this.row) { 
     return false; 
    } 
    return true; 
} 

public int hashCode() { 
    int result = 7; 
    result += row * 31; 
    result += col * 31; 
    return result; 
}

遍歷列表

你不必自己做迭代，但是這正是呼籲List.contains會做。這一個很容易：

if (!myList.contains(node)) { 
    myList.add(node); 
}

這將爲你迭代，所以你不必編寫循環。

目錄設置到列表

這裏有兩個子選項。如果您想保留輸入列表的順序，那麼您可以使用LinkedHashSet。如果你不在乎，你可以使用HashSet。我的意思是，如果我有一個List與元素A，B，C，將其轉換爲HashSet和後面可能會產生一個不同的列表，如B，C，A LinkedHashSet保持元素按插入順序，避免此問題。在任何情況下，你只是這樣做：

Set<Node> nodeSet = new [Linked]HashSet<Node>(myList); 
nodeSet.add(node); 
myList = new ArrayList<Node>(nodeSet);

請記住，這基本上是做迭代爲好，但它使用哈希碼的快捷方式，而不是檢查每一個元素的平等，這可能是一個大問題與足夠的節點。如果你的節點列表很小（少於1000個元素），那麼我懷疑這會造成很大的不同，你也可以使用第一個。

轉換一切Set

您剛纔提到，這將需要大量的重構你的代碼，但是這並不是一件壞事，特別是如果你打算在這個代碼的工作很多未來。我的經驗法則是，如果重構會使代碼更容易維護，那麼添加一點額外的開發時間就是從來沒有一件壞事。編寫可維護，可讀和易懂的代碼is what the experts do（這裏的問題不相關，但是這個特定的答案是）。由於Set意味着獨特的元素，並且List不會，因此進行更改是有意義的。編譯器幾乎可以告訴你所有的地方你必須改變它的錯誤，並且可能比你想象的要更少的時間。

來源

2012-11-06 15:12:56 Brian

換句話說。爲了保持它更乾淨，我應該重構爲'Set'並覆蓋'equals（）'方法？ – JavaCake

和'hashCode（）'，但是。 – Brian

即使它變成了'O（N）'，我仍然很想穿越整個列表。 – JavaCake

將所有元素添加到新的Set，然後將Set中的所有元素添加到新的List。這將使它。

來源

2012-11-06 14:47:53 dounyy

不要忘記重寫equal（）和hashCode（）方法來檢查你想實現的相等的具體條件 – JTMon

當他們要求唯一性時，我總是發現奇怪的事情，當人們想要使用List（我猜爲get(int)方法）時，只有通過Set才能實現。

總之，通過操縱一個小等號/哈希碼（使平等返回true時row和col是相同的）方法，並添加調用List#contains(Object)，你可以讓你的目標不sacrifying您的List

EDIT達到

請注意，您也可以創建一個比較器並依靠Collections#sort(List, Comparator)將您的列表排序並將具有相同值的項目融合爲僅一個值。

來源

2012-11-06 14:51:17 Riduidel

我已經有了一個排序算法，但我排序了一個完全不同的標準。所以也許我可能會更好地使用Set來代替。 – JavaCake

添加在節點如果可能的equals方法：

@Override 
public boolean equals(Node n){ 
if(this.getRow().equals(n.getRow()) && this.getCol().equals(n.getCol()) 
return true; 
else 
return false; 
}

然後用list-to-set-to-list伎倆。

試試這個方法：

List<Node> removeDuplicateNodes(List<Node> inputList){ 
return (inputList ==null or inputList.size()==0)? Collections.EMPTY_LIST: new ArrayList<Node>(new HashSet<Node>(inputList)); 
}

更新：

如果你wan't保持輸入順序，使用LinkedHashSet

List<Node> removeDuplicateNodes(List<Node> inputList){ 
return (inputList ==null or inputList.size()==0)? Collections.EMPTY_LIST: new ArrayList<Node>(new LinkedHashSet<Node>(inputList)); 
}

來源

2012-11-06 14:51:22

理想情況下，你會使用Set，但是如果你想避免重新實現你的數據結構從ArrayList<Node>到Set，你可以impl作爲網守Set：

每次元素即將被插入到您的ArrayList中時，檢查行 - col對是否已經在Set中。
如果不是，註冊行山坳對進入設置
如果對已經設定的存在，不插入
每一次的內容是關於從ArrayList中移除，從中刪除集合。

因此它是一個「把關人」。

所有Set操作都是O（1），因爲它們被散列;根據需要進行最小限度的重構和無惡意的循環。

來源

2012-11-06 14:52:22

如果我實現Set，我如何過濾基於'row'和'col'的重複項而不是整個元素？ – JavaCake

嗯，似乎配對<>只在C++中，而不是Java。您可以通過覆蓋'Node'的'.equals（）'來過濾重複項：您在哪裏檢查行和列是否相等，然後節點本身是相等的。 –

但是，通過重寫equals方法，以相同的方式使用'ArrayList'是不可能的？ – JavaCake

保持一個集合和一個列表。使用設置來檢查重複項。如果沒有重複，則添加到Set和List。

...假設節點定義了一個.equals方法...

private final Set<Node> seen = new HashMap<Node>(); 
private final List<Node> uniqueNodes = new ArrayList<Node>(); 


public void insertIfUnique(final Node n) { 
    if (seen.contains(n)) { 
    return; 
    } 
    seen.add(n); 
    uniqueNodes.add(n); 
}

來源

2012-11-06 14:54:01

消除或避免加入重複在與ArrayList的自定義對象

回答

相關問題