anybody know an efficient way to decide if two arraylists contain the same values?
Code:
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
the challenge is that the arraylists has not the same value order..
(foo, baa) == (foo, baa) // per definition :)
i need to get this
(foo, baa) == (baa, foo) // true
so what would be your approach?
先排序就行了。
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) 中运行，但我们可以做得更好。首先执行空值和大小比较。然后使用 aHashMap<String, Integer>并将特定字符串的频率存储为值。对两个列表执行此操作并检查地图的大小是否相同。然后遍历其中一个映射，对于每个条目，检查另一个映射是否包含字符串并且具有相同的频率。这种方法是 O(n) 平均情况。
假设列表不包含重复项，您可以为此使用两个临时HashSet<String>对象。
String从您要比较的两个s构造 s 集合ArrayList<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>制作并比较相应的频率计数器。
最有效的方法取决于数组的大小。
对于非常小的列表，使用contains()可能是最有效的。（也许对于包含 0 到 5 个元素的列表......我猜。）
对于中型到大型列表，您可以：
对两个数组列表进行排序并成对比较它们，
对一个列表进行排序并使用二进制搜索来探测第二个列表中的值。
将一个转换为 HashSet 并使用第二个中的值进行探测。
复杂性分析不是直截了当的，因为它取决于列表是否相等的可能性……与否。“最坏的情况”是当列表相等时，因为这意味着您必须先检查所有元素才能返回true。在这种情况下，复杂度分别为O(N^2)、和。 O(NlogN)O(NlogN)O(N)
这没有考虑空间使用情况，以及（在 Java 中）使用大量内存对性能的影响，
还有“比例常数”的问题；例如O(NlogN)，可以比O(N). 的小值更快N。
简而言之……没有一种单一的解决方案总是最好的。
您应该对两个 ArrayList 进行排序，然后进行相等比较。但是，您可能需要删除重复项（我不确定您的重复项政策）。
这里您有 Java 8，请说明您是否需要 Java 7 解决方案。
假设 1：ArrayLists 不是空值。
它的时间复杂度是 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
通过使用比较链，
希望这对你有用。
问候阿肖克·古迪斯。
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;
}