Java: 判断ArrayList是否包含有重复值的ArrayList

Question

我目前正在尝试创建一个方法，确定ArrayList(a2)是否包含一个ArrayList(a1)，假设两个列表都包含重复值（containsAll不起作用，因为如果一个ArrayList包含重复值，则无论值的数量如何，它都会返回true）

这是我拥有的代码：（我相信它会工作，但是我不能在for循环内使用.remove）

public boolean isSubset(ArrayList<Integer> a1, ArrayList<Integer> a2) {
    Integer a1Size= a1.size();
    for (Integer integer2:a2){
        for (Integer integer1: a1){
            if (integer1==integer2){
                a1.remove(integer1);
                a2.remove(integer2);
                if (a1Size==0){
                    return true;
                }
            }
        }
    }
    return false;
}

感谢您的帮助。

- Luke Mann

---

这两个列表中的项目顺序重要吗？ - GuiSim

a1Size的值只被计算一次（在循环之前），因此基于它的值的逻辑是无意义的。 - Scary Wombat

要从ArrayList中移除元素，请使用迭代器。 - Scary Wombat

为什么不直接使用 removeAll 呢？ - njzk2

听起来像是集合交集。 - Amir Afghani

Answer 1

更新

我认为您问题最清晰的陈述在您的评论中：

是的，示例 " Example: [dog,cat,cat,bird] is a match for containing [cat,dog] is false but containing [cat,cat,dog] is true?" 正是我想要实现的。

所以实际上，您不是在寻找“子集”，因为它们不是集合。它们可以包含重复的元素。您真正想说的是，您想查看 a1 是否包含所有 a2 的元素，并且这些元素出现的次数相同。

一种方法是计算两个列表中的所有元素的数量。我们可以使用此方法获取这样的计数：

private Map<Integer, Integer> getCounter (List<Integer> list) {
    Map<Integer, Integer> counter = new HashMap<>();
    for (Integer item : list) {
        counter.put (item, counter.containsKey(item) ? counter.get(item) + 1 : 1);
    }
    return counter;
}

我们将重命名您的方法为containsAllWithCounts()，并使用getCounter()作为辅助工具。您的方法还将接受List对象作为其参数，而不是ArrayList对象：指定参数为接口而不是实现是一个好习惯，这样您就不会被绑定到使用ArrayList类型。

考虑到这一点，我们简单地扫描a2中项目的计数，并查看它们在a1中是否相同：

  public boolean containsAllWithCounts(List<Integer> a1, List<Integer> a2) {
        Map<Integer,Integer> counterA1 = getCounter(a1);
        Map<Integer,Integer> counterA2 = getCounter(a2);

        boolean containsAll = true;
        for (Map.Entry<Integer, Integer> entry : counterA2.entrySet ()) {
            Integer key = entry.getKey();
            Integer count = entry.getValue();
            containsAll &= counterA1.containsKey(key) && counterA1.get(key).equals(count);
            if (!containsAll) break;
        }

        return containsAll;
    }

如果您愿意的话，我可以使用Java泛型重写此代码以处理任意类型，而不仅仅是 Integer 对象。另外，所有的代码都可以使用Java 8流缩短（我最初使用了它-请参见下面的注释）。只需在评论中告诉我即可。

- sparc_spread

---

@sparc-spread 如果我们使用Java 7、6呢？顺便说一下，也许他应该从易到难开始？ - ceph3us

Answer 2

如果您想从列表中删除元素，有两种选择：

• 迭代复制品
• 使用并发列表实现

另请参阅：

http://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#synchronizedList-java.util.List-

顺便问一下，为什么你不覆盖contains方法？

在这里，您使用简单的对象，例如"Integer"，那么当您使用List< SomeComplexClass >时会怎样呢？

例如使用迭代器删除：

    List<Integer> list1 = new ArrayList<Integer>();
    List<Integer> list2 = new ArrayList<Integer>();

    List<Integer> listCopy = new ArrayList<>(list1);
    Iterator<Integer> iterator1 = listCopy.iterator();
    while(iterator1.hasNext()) {
        Integer next1 = iterator1.next();
        Iterator<Integer> iterator2 = list2.iterator();
        while (iterator2.hasNext()) {
            Integer next2 = iterator2.next();
            if(next1.equals(next2)) list1.remove(next1);
        }
    }

另外关于迭代器的问题，请参见以下答案:

Concurrent Modification exception

同时，不要使用“==”运算符来比较对象 :) 而是使用equal方法

关于使用removeAll()和其他类似方法：

请记住，许多实现列表接口的类不会覆盖列表接口中的所有方法 - 因此您可能会遇到不支持的操作异常 - 因此在这种情况下我更喜欢“低级别”的二进制/线性/混合搜索。

对于复杂类对象的比较，您需要重写equal和hashCode方法

如果您想删除重复值，只需将ArrayList放入HashSet中即可。它将根据您对象的equals（）方法删除重复项。 - Olga

在Java中，HashMap通过使用hashCode来定位桶。每个桶是驻留在其中的项目列表。使用equals进行比较扫描项目。当添加项目时，一旦达到某个负载百分比，HashMap就会调整大小。

因此，有时它必须与几个项进行比较，但通常它比O(n)更接近O(1)。

简而言之-没有必要使用更多资源（内存）和“利用”不必要的类 - 因为随着项目计数增长，哈希映射“获取”方法变得非常昂贵。

  hashCode -> put to bucket  [if many item in bucket] -> get  = linear scan 

  so  what counts in removing items ? 

复杂性等于和哈希码以及使用适当的算法进行迭代

- ceph3us

Answer 3

如果您想要移除重复的值，只需将ArrayList放入HashSet中即可。它会根据对象的equals()方法来移除重复项。

- Olga

Answer 4

我知道这可能有点业余，但是...

没有必要从两个列表中都删除项目，所以只需从一个列表中取出即可。

public boolean isSubset(ArrayList<Integer> a1, ArrayList<Integer> a2) {
    for(Integer a1Int : a1){
        for (int i = 0; i<a2.size();i++) {
            if (a2.get(i).equals(a1Int)) {
                a2.remove(i);
                break;
            }
        }
        if (a2.size()== 0) {

            return true;
        }
    }
    return false;
}

- David D.