有人知道一种有效的方法来判断两个arraylist是否包含相同的值吗？
代码：
ArrayList<String> dummy1= new ArrayList<String>();
list1.put("foo");
list1.put("baa");
ArrayList<String> dummy2= new ArrayList<String>();
list1.put("baa");
list1.put("foo");
dummy1 == dummy2
挑战在于ArrayLists中没有相同的数值顺序。
(foo, baa) == (foo, baa) // per definition :)
我需要得到这个。
(foo, baa) == (baa, foo) // true
那么你的解决方案是什么？
先将其排序。
public boolean equalLists(List<String> one, List<String> two){
if (one == null && two == null){
return true;
}
if((one == null && two != null)
|| one != null && two == null
|| one.size() != two.size()){
return false;
}
//to avoid messing the order of the lists we will use a copy
//as noted in comments by A. R. S.
one = new ArrayList<String>(one);
two = new ArrayList<String>(two);
Collections.sort(one);
Collections.sort(two);
return one.equals(two);
}
说实话，你应该检查一下你的数据结构选择。这似乎更像是一个集合问题。排序然后比较需要O(nlog n)，而使用HashSet进行比较只需要O(n)。
sort方法的时间复杂度为O(n log n)，但我们可以做得更好。首先进行null和size比较。然后使用HashMap<String, Integer>，将特定字符串的频率存储为值。对于两个列表都要执行此操作，并检查映射的大小是否相同。然后遍历其中一个映射，在每个条目中，检查另一个映射是否包含该字符串并具有相同的频率。这种方法平均情况下的时间复杂度为O(n)。
map.get() 的时间复杂度为 O(n)。 - aioobemap.get() is O(1) - Kevin Dixson假设列表中没有重复项，你可以使用两个临时HashSet<String>对象。
从要比较的两个ArrayList<String>构建String集，然后检查第一个集合是否包含第二个列表中的所有项目，并且第二个集合是否包含第一个列表中的所有项目。
你可以这样实现：
List<String> a = ...;
List<String> b = ...;
Set<String> setA = new HashSet<String>(a);
Set<String> setB = new HashSet<String>(b);
boolean same = setA.containsAll(b) && setB.containsAll(a);
HashSet<String>替换为HashMap<String,Integer>来创建并比较相应的频率计数器。(a, b) == (b, a, b) == (b, b, b, a)。 - Mike Strobel最有效的方式取决于数组的大小。
对于非常小的列表，使用contains()可能是最有效的。(对于0到5个元素之间的列表…我猜测。)
对于中到大型的列表，您可以：
对两个数组列表进行排序并逐对比较它们，
对一个列表进行排序并使用二进制搜索来探测第二个列表中的值。
将其中一个列表转换为HashSet，并使用第二个列表中的值进行探测。
复杂性分析并不直接，因为它取决于列表是否相等...或者不相等。 "最坏情况"是列表相等，因为这意味着您必须检查所有元素才能返回true。在这种情况下，复杂度分别为O(N^2)、O(NlogN)、O(NlogN)和O(N)。
这没有考虑空间使用情况，以及（在Java中）使用大量内存的性能影响,
还存在“比例常数”的问题； 例如O(NlogN)对于小的N值可能比O(N)更快。
简而言之...没有一种单一的解决方案始终是最好的。
您需要对这两个ArrayList进行排序，然后进行相等比较。不过，您可能需要删除重复项（我不确定您的重复项策略）。
这里有一个Java 8版本的解决方案，请说明是否需要Java 7版本的解决方案。
假设1：ArrayList不为空。
时间复杂度为O(N)，其中N是任意输入的大小。
除了输入之外，其内存复杂度为0(N)。
换句话说，它的时间和内存复杂度都是线性的。
理论上，您可以拥有恒定的O(1)内存复杂度，但这需要从a1中删除元素并将它们添加到setA1中。在我看来，这太过依赖垃圾收集器，因此希望这个解决方案对您足够。
import java.util.*;
public class ArraySameValuesSolver {
public boolean of(List<String> list1, List<String> list2) {
if (list1.size() != list2.size())
return false;
Map<String, Integer> occ = new HashMap<>();
list1.stream().forEach(s -> incrementOccurences(occ, s));
for (String s: list2) {
decrementOccurrences(occ, s);
if (occ.get(s) < 0)
return false;
}
return true;
}
private void incrementOccurences(Map<String, Integer> occ, String s) {
if (!occ.containsKey(s))
occ.put(s, 1);
else
occ.put(s, occ.get(s) + 1);
}
private void decrementOccurrences(Map<String, Integer> occ, String s) {
if (!occ.containsKey(s))
occ.put(s, -1);
else
occ.put(s, occ.get(s) - 1);
}
}
http://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained
通过使用比较链，
希望这对您有用。
祝好， Ashok Gudise。
public boolean isListEquals( List listA , List listB ) {
boolean result = false;
if ( ( listA == listB ) ) {
result = true;
return result;
}
if ( ( listA == null ) || ( listB == null ) ) {
return result;
}
if ( listA.size() != listB.size() ) {
return result;
}
List listC = new ArrayList( listA );
listC.removeAll( listB );
if ( listC.size() > 0 ) {
return result;
}
result = true;
return result;
}
arraylists是否具有相同的元素。因此，你最好能做到的就是O(N)。 - Prateekif(a,b)==(b,a,b)），则情况变得更加复杂，因为size()比较变得无意义，然后必须检查散列表中存在但第二个序列中不存在的元素。 - Mike Strobel