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

col和变量是唯一的row，并且只能在 中出现一次ArrayList<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

这里有两个子选项。如果要保留输入列表的顺序，则可以使用LinkedHashSet. 如果你不在乎，你可以使用HashSet. 我的意思是，如果我有一个List带有元素 A、B、C 的 a，将其转换为 aHashSet并返回可能会产生一个不同的列表，例如 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，然后将所有元素从Set一个新的List。那会成功的。

于 2012-11-06T14:47:53.310 回答
0

我总是觉得奇怪的是，当人们需要唯一性时，他们想要使用 a List（get(int)我猜是该方法），而这只能通过Set.

无论如何，通过稍微操作 equals/hashcode（使 equalstrue在相row同时返回col）方法并添加对 的调用List#contains(Object)，您可以在不牺牲您的情况下达到目标List

编辑

请注意，您还可以创建一个 Comparator 并依靠它对Collections#sort(List, Comparator)列表进行排序，并将具有相同值的项目融合为一个值。

于 2012-11-06T14:51:17.270 回答
0

理想情况下，您会使用Set，但如果您想避免从ArrayList<Node>to重新实现数据结构Set，您可以将其实现Set为看门人：

  • 每次将元素插入到 ArrayList 中时，检查行-列对是否已经在 Set 中。
  • 如果没有，将 row-col 对注册到 Set
  • 如果该对已经存在于集合中，则不要插入它
  • 每次要从 ArrayList 中删除元素时，将其从 Set 中删除。

因此它是一个“看门人”。

所有的 Set 操作都是O(1)因为它们是散列的；最少的重构，没有需要的讨厌的循环。

于 2012-11-06T14:52:22.947 回答
0

保留一个集合和一个列表。使用 Set 检查重复项。如果没有重复，则添加到 Set 和 List 中。

...假设 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 回答