2

この構造にカスタム オブジェクトがあります

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

および変数は一意であり、 内で 1 回だけ使用できcolます。rowArrayList<Node> myList

厄介なforループを作成することなく、重複の可能性を追加またはチェックすることを回避する最適な方法はありますか?

重複が発生しないため、インターフェースがこれに対する解決策になる可能性があることは承知していSetますが、現在、必要にならない限りリファクタリングしたくないコードがたくさんあります。

4

6 に答える 6

5

ここにあなたのオプションがあります。これらのソリューションはすべて、 と を適切に実装する必要が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

自分で繰り返しを行う必要はありませんが、それはまさに呼び出しList.containsが行うことです。これはとても簡単です：

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

これは繰り返されるため、ループを記述する必要はありません。

ListにSet_List

ここには 2 つのサブオプションがあります。入力リストの順序を保持したい場合は、 を使用できますLinkedHashSet。気にしない場合は、そのまま使用できますHashSet。つまりList、要素 A、B、C を持つ a がある場合、それを a に変換してHashSet戻すと、B、C、A などの別のリストが生成される可能性があります。LinkedHashSet要素を挿入順序で保持し、この問題を回避します。いずれにせよ、これを行うだけです：

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

これは基本的に繰り返し処理も行っていますが、すべての要素の等価性をチェックする代わりにハッシュ コード ショートカットを使用していることに注意してください。ノード リストが小さい場合 (1000 要素未満)、これが大きな違いを生むとは思えず、最初のものを使用することもできます。

すべてをに変換するSet

これにはコードで多くのリファクタリングが必要になるとおっしゃいましたが、これは悪いことではありません。特に、将来このコードで多くの作業を行う予定がある場合はなおさらです。私の経験則では、リファクタリングによってコードの保守が容易になるのであれば、少し余分な開発時間を追加することは決して悪いことではありません。保守しやすく、読みやすく、理解しやすいコードを書くことは、専門家が行うことです(ここでの質問は関係ありませんが、この特定の回答は関係があります)。Setユニークな要素を意味し、そうではないのでList、変更を加えるのは理にかなっています。コンパイラは、エラーで変更する必要があるすべての場所をほぼ教えてくれるので、思ったよりも時間がかからないかもしれません。

于 2012-11-06T15:12:56.823 に答える
1

可能であれば Node に 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));
}

アップデート ：

入力順序を維持したくない場合は、使用します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-06T14:51:22.577 に答える
0

セットとリストの両方を保持します。Set を使用して重複をチェックします。重複がない場合は、セットとリストの両方に追加します。

... Node に .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-06T14:54:01.987 に答える
0

を使用するのが理想的ですが、 からまでSetのデータ構造を再実装したくない場合は、ゲートキーパーとして実装できます。ArrayList<Node>SetSet

  • 要素が ArrayList に挿入されるたびに、行と列のペアが既に Set にあるかどうかを確認します。
  • そうでない場合は、行と列のペアをセットに登録します
  • ペアがセットに既に存在する場合は、挿入しないでください
  • 要素が ArrayList から削除されるたびに、Set から削除します。

したがって、それは「ゲートキーパー」です。

すべての Set 操作はO(1)、ハッシュされているためです。必要に応じて最小限のリファクタリングと厄介なループはありません。

于 2012-11-06T14:52:22.947 に答える
0

すべての要素を new に追加してから、Setすべての要素を からSetnewに追加しListます。それで間に合います。

于 2012-11-06T14:47:53.310 に答える
0

ユニシティが必要なときにList(メソッドについては、おそらく)を使用したいというケースを見ると、私はいつも奇妙に感じます。get(int)Set

とにかく、equals/hashcode (equals return truewhenrowとcolare the same) メソッドを少し操作し、 への呼び出しを追加することList#contains(Object)で、List

編集

Comparator を作成Collections#sort(List, Comparator)して、リストをソートし、同じ値を持つ項目を 1 つの値に統合することもできます。

于 2012-11-06T14:51:17.270 に答える