Java比较无序的ArrayLists
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20054737/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java compare unordered ArrayLists
提问by Alex Tape
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?
那么你的方法是什么？
采纳答案by frankie liuzzi
Just sort it first.
先排序就好了
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);
}
Honestly, you should check your data structure decision. This seems more like a set problem. Sorting then comparing will take O(nlog n) while a HashSetcomparison will only be O(n).
老实说，您应该检查您的数据结构决策。这似乎更像是一个集合问题。排序然后比较将花费 O(nlog n) 而HashSet比较将只需要 O(n)。
回答by But I'm Not A Wrapper Class
You should sort the two ArrayLists, then do an equal comparison. However, you may need to remove duplicates (I'm not sure about your policy on duplicates).
您应该对两个 ArrayList 进行排序，然后进行相等的比较。但是，您可能需要删除重复项（我不确定您对重复项的政策）。
回答by Zong
The sort method runs in O(n log n) but we can do better. First perform null and size comparisons. Then use a HashMap<String, Integer>and store the frequency of a particular string as the value. Do this for one of the lists, then iterate through the other and check that the map contains the string and has the same frequency. This method is O(n).
sort 方法在 O(n log n) 中运行，但我们可以做得更好。首先执行空值和大小比较。然后使用 aHashMap<String, Integer>并将特定字符串的频率存储为值。对其中一个列表执行此操作，然后遍历另一个列表并检查该映射是否包含该字符串并具有相同的频率。这种方法是 O(n)。
回答by dasblinkenlight
Assuming that the lists contain no duplicates, you can use two temporary HashSet<String>objects for that.
假设列表不包含重复项，您可以HashSet<String>为此使用两个临时对象。
Construct sets of Strings from both ArrayList<String>s that you are comparing, and then check that the first set has all items from the second list, and also the second set contains all items from the first list.
String从ArrayList<String>要比较的两个s构造s 的集合，然后检查第一个集合是否包含第二个列表中的所有项目，并且第二个集合是否包含第一个列表中的所有项目。
You can do it like this:
你可以这样做：
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);
If you must account for duplicates, replace HashSet<String>with HashMap<String,Integer>to make and compare the corresponding frequency counters.
如果你必须考虑重复，替代HashSet<String>与HashMap<String,Integer>制作和比较相应的频率计数器。
回答by Ashok Gudise
You can find your anser here,
你可以在这里找到你的分析器，
http://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained
http://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained
By Using Compare chain,
通过使用比较链，
Hope this will work for you.
希望这对你有用。
Regards Ashok Gudise.
问候阿肖克·古迪斯。
回答by Stephen C
The most efficient way depends on the size of the array.
最有效的方法取决于数组的大小。
For very small lists, using
contains()is probably most efficient. (Maybe for lists with between 0 to 5 elements ... I'd guess.)For medium to large sized lists you can either:
sort the both array lists and compare them pair-wise,
sort one list and use binary search to probe the values in the second one.
convert one to a HashSet and probe with the values in the second one.
对于非常小的列表，使用
contains()可能是最有效的。（也许对于 0 到 5 个元素之间的列表......我猜。）对于大中型列表，您可以：
对两个数组列表进行排序并成对比较，
对一个列表进行排序并使用二分搜索来探测第二个列表中的值。
将一个转换为 HashSet 并使用第二个中的值进行探测。
The complexity analysis is not straight-forward as it depends on the likelihood that the lists are equal ... or not. The "worst case" is when the lists are equal, because that means that you have to check all elements before you can return true. In that case the complexities are O(N^2), O(NlogN), O(NlogN)and O(N)respectively.
复杂性分析不是直截了当的，因为它取决于列表相等的可能性......或不相等。“最坏的情况”是当列表相等时，因为这意味着您必须在返回之前检查所有元素true。在这种情况下，复杂性是O(N^2)，O(NlogN)，O(NlogN)和O(N)分别。
That doesn't take into account space usage, and (in Java) the performance impact of using a lot of memory,
这没有考虑空间使用情况，以及（在 Java 中）使用大量内存的性能影响，
There is also the issue of the "constants of proportionality"; e.g. O(NlogN)can be faster than O(N)for small values of N.
还有“比例常数”的问题；例如，O(NlogN)可以比O(N)的小值更快N。
In short ... there is no single solution that is always going to be best.
简而言之......没有任何单一的解决方案总是最好的。
回答by Benny Iskandar
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;
}
回答by GA1
Here you have a Java 8, please specify if you need a Java 7 solution.
这里有 Java 8，请说明是否需要 Java 7 解决方案。
Assumption 1: The ArrayLists are not nulls.
假设 1：ArrayLists 不是空值。
Its time complexity is O(N), where Nis the size of any of the inputs.
它的时间复杂度是 O(N)，其中N是任何输入的大小。
Its memory complexity in addition to the input is 0(N)
它的内存复杂度除了输入是0(N)
In other words, its time and memory complexity are linear.
换句话说，它的时间和内存复杂度是线性的。
Theoretically you could have a constant O(1)memory complexity, but it would involve removing elements from the a1while adding them to the setA1. In my opinion, this relies too much on garbage collector so hopefully this solution will be enough for you.
理论上你可以有一个恒定的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);
}
}
