java - 如何检查一个列表是否与另一个列表具有相同的元素，能够有重复

Question

我有 2 个包含不同类型城市名称的列表:

ArrayList<City> list1 = new ArrayList<City>();
ArrayList<City> list2 = new ArrayList<City>();


list1.add(Birmingham);
list1.add(Amsterdam);
list1.add(Rotterdam);
list1.add(Brussels);

list2.add(Brussels);
list2.add(Brussels);
list2.add(Rotterdam);
list2.add(Amsterdam);
list2.add(Amsterdam);

如果我比较这两个列表，它应该是true

如果我有第三个列表:

list3.add(brussELtss);
list3.add(Rotterdam);
list3.add(Amsterdam);

如果我将第三个列表与前两个列表中的任何一个进行比较，它应该是错误

我尝试过比较、等于和包含所有，但这不起作用。

Answer 1

您有set为此，请查看 Hashset将包含唯一元素的实现。您的对象 City 需要实现 Comparable/Comparator 来决定是否相等。在集合中添加第一个元素，然后开始添加第二个列表，如果 add 方法返回 true 则元素已经存在

更新:-阅读评论后，我可以想到低于 O(n) 时间复杂度的算法

1. 迭代第一个列表并构造一个以元素为键、计数为值的映射(HashMap 作为实现)

2. 迭代第二个列表，如果元素不存在于映射中，则它们不相等。

3. 如果找到元素，则将映射中该元素的计数减一

4. 最后迭代map，如果有一个元素的count不为零，则list不相等