Intersection and union of ArrayLists in Java
JavaListUnionIntersectionJava Problem Overview
Are there any methods to do so? I was looking but couldn't find any.
Another question: I need these methods so I can filter files.
Some are AND
filters and some are OR
filters (like in set theory), so I need to filter according to all files and the unite/intersects ArrayLists that holds those files.
Should I use a different data structure to hold the files? Is there anything else that would offer a better runtime?
Java Solutions
Solution 1 - Java
Here's a plain implementation without using any third-party library. Main advantage over retainAll
, removeAll
and addAll
is that these methods don't modify the original lists input to the methods.
public class Test {
public static void main(String... args) throws Exception {
List<String> list1 = new ArrayList<String>(Arrays.asList("A", "B", "C"));
List<String> list2 = new ArrayList<String>(Arrays.asList("B", "C", "D", "E", "F"));
System.out.println(new Test().intersection(list1, list2));
System.out.println(new Test().union(list1, list2));
}
public <T> List<T> union(List<T> list1, List<T> list2) {
Set<T> set = new HashSet<T>();
set.addAll(list1);
set.addAll(list2);
return new ArrayList<T>(set);
}
public <T> List<T> intersection(List<T> list1, List<T> list2) {
List<T> list = new ArrayList<T>();
for (T t : list1) {
if(list2.contains(t)) {
list.add(t);
}
}
return list;
}
}
Solution 2 - Java
Collection (so ArrayList also) have:
col.retainAll(otherCol) // for intersection
col.addAll(otherCol) // for union
Use a List implementation if you accept repetitions, a Set implementation if you don't:
Collection<String> col1 = new ArrayList<String>(); // {a, b, c}
// Collection<String> col1 = new TreeSet<String>();
col1.add("a");
col1.add("b");
col1.add("c");
Collection<String> col2 = new ArrayList<String>(); // {b, c, d, e}
// Collection<String> col2 = new TreeSet<String>();
col2.add("b");
col2.add("c");
col2.add("d");
col2.add("e");
col1.addAll(col2);
System.out.println(col1);
//output for ArrayList: [a, b, c, b, c, d, e]
//output for TreeSet: [a, b, c, d, e]
Solution 3 - Java
This post is fairly old, but nevertheless it was the first one popping up on google when looking for that topic.
I want to give an update using Java 8 streams doing (basically) the same thing in a single line:
List<T> intersect = list1.stream()
.filter(list2::contains)
.collect(Collectors.toList());
List<T> union = Stream.concat(list1.stream(), list2.stream())
.distinct()
.collect(Collectors.toList());
If anyone has a better/faster solution let me know, but this solution is a nice one liner that can be easily included in a method without adding a unnecessary helper class/method and still keep the readability.
Solution 4 - Java
list1.retainAll(list2) - is intersection
union will be removeAll
and then addAll
.
Find more in the documentation of collection(ArrayList is a collection) http://download.oracle.com/javase/1.5.0/docs/api/java/util/Collection.html
Solution 5 - Java
Unions and intersections defined only for sets, not lists. As you mentioned.
Check guava library for filters. Also guava provides real intersections and unions
static <E> Sets.SetView<E >union(Set<? extends E> set1, Set<? extends E> set2)
static <E> Sets.SetView<E> intersection(Set<E> set1, Set<?> set2)
Solution 6 - Java
You can use CollectionUtils
from apache commons.
Solution 7 - Java
The solution marked is not efficient. It has a O(n^2) time complexity. What we can do is to sort both lists, and the execute an intersection algorithm as the one below.
private static ArrayList<Integer> interesect(ArrayList<Integer> f, ArrayList<Integer> s) {
ArrayList<Integer> res = new ArrayList<Integer>();
int i = 0, j = 0;
while (i != f.size() && j != s.size()) {
if (f.get(i) < s.get(j)) {
i ++;
} else if (f.get(i) > s.get(j)) {
j ++;
} else {
res.add(f.get(i));
i ++; j ++;
}
}
return res;
}
This one has a complexity of O(n log n + n) which is in O(n log n). The union is done in a similar manner. Just make sure you make the suitable modifications on the if-elseif-else statements.
You can also use iterators if you want (I know they are more efficient in C++, I dont know if this is true in Java as well).
Solution 8 - Java
I think you should use a Set
to hold the files if you want to do intersection and union on them. Then you can use Guava's Sets class to do union
, intersection
and filtering by a Predicate
as well. The difference between these methods and the other suggestions is that all of these methods create lazy views of the union, intersection, etc. of the two sets. Apache Commons creates a new collection and copies data to it. retainAll
changes one of your collections by removing elements from it.
Solution 9 - Java
Here is a way how you can do an intersection with streams (remember that you have to use java 8 for streams):
List<foo> fooList1 = new ArrayList<>(Arrays.asList(new foo(), new foo()));
List<foo> fooList2 = new ArrayList<>(Arrays.asList(new foo(), new foo()));
fooList1.stream().filter(f -> fooList2.contains(f)).collect(Collectors.toList());
An example for lists with different types. If you have a realtion between foo and bar and you can get a bar-object from foo than you can modify your stream:
List<foo> fooList = new ArrayList<>(Arrays.asList(new foo(), new foo()));
List<bar> barList = new ArrayList<>(Arrays.asList(new bar(), new bar()));
fooList.stream().filter(f -> barList.contains(f.getBar()).collect(Collectors.toList());
Solution 10 - Java
You can use commons-collections4 CollectionUtils
Collection<Integer> collection1 = Arrays.asList(1, 2, 4, 5, 7, 8);
Collection<Integer> collection2 = Arrays.asList(2, 3, 4, 6, 8);
Collection<Integer> intersection = CollectionUtils.intersection(collection1, collection2);
System.out.println(intersection); // [2, 4, 8]
Collection<Integer> union = CollectionUtils.union(collection1, collection2);
System.out.println(union); // [1, 2, 3, 4, 5, 6, 7, 8]
Collection<Integer> subtract = CollectionUtils.subtract(collection1, collection2);
System.out.println(subtract); // [1, 5, 7]
Solution 11 - Java
- retainAll will modify your list
- Guava doesn't have APIs for List (only for set)
I found ListUtils very useful for this use case.
Use ListUtils from org.apache.commons.collections if you do not want to modify existing list.
ListUtils.intersection(list1, list2)
Solution 12 - Java
In Java 8, I use simple helper methods like this:
public static <T> Collection<T> getIntersection(Collection<T> coll1, Collection<T> coll2){
return Stream.concat(coll1.stream(), coll2.stream())
.filter(coll1::contains)
.filter(coll2::contains)
.collect(Collectors.toSet());
}
public static <T> Collection<T> getMinus(Collection<T> coll1, Collection<T> coll2){
return coll1.stream().filter(not(coll2::contains)).collect(Collectors.toSet());
}
public static <T> Predicate<T> not(Predicate<T> t) {
return t.negate();
}
Solution 13 - Java
One-liners since Java 8
> import static java.util.stream.Stream.concat;
> import static java.util.stream.Collectors.toList;
> import static java.util.stream.Collectors.toSet;
Union if there are no duplicates:
return concat(a.stream(), b.stream()).collect(toList());
Union and distinct:
return concat(a.stream(), b.stream()).distinct().collect(toList());
Union and distinct if Collection/Set return type:
return concat(a.stream(), b.stream()).collect(toSet());
Intersect if no duplicates:
return a.stream().filter(b::contains).collect(toList());
If collection b
is huge and not O(1), then pre-optimize filter performance by adding 1 line before return
. Copy to HasSet
(import java.util.Set;
):
> ... b = Set.copyOf(b);
Intersect and distinct:
return a.stream().distinct().filter(b::contains).collect(toList());
Solution 14 - Java
If the objects in the list are hashable (i.e. have a decent hashCode and equals function), the fastest approach between tables approx. size > 20 is to construct a HashSet for the larger of the two lists.
public static <T> ArrayList<T> intersection(Collection<T> a, Collection<T> b) {
if (b.size() > a.size()) {
return intersection(b, a);
} else {
if (b.size() > 20 && !(a instanceof HashSet)) {
a = new HashSet(a);
}
ArrayList<T> result = new ArrayList();
for (T objb : b) {
if (a.contains(objb)) {
result.add(objb);
}
}
return result;
}
}
Solution 15 - Java
I was also working on the similar situation and reached here searching for help. Ended up finding my own solution for Arrays.
ArrayList
Note : Posting this if it can help someone reaching this page for help.
ArrayList<String> AbsentDates = new ArrayList<String>();//This Array will store difference
public void AbsentDays() {
findDates("April", "2017");//Array one with dates in Month April 2017
findPresentDays();//Array two carrying some dates which are subset of Dates in Month April 2017
for (int i = 0; i < Dates.size(); i++) {
for (int j = 0; j < PresentDates.size(); j++) {
if (Dates.get(i).equals(PresentDates.get(j))) {
Dates.remove(i);
}
}
AbsentDates = Dates;
}
System.out.println(AbsentDates );
}
Solution 16 - Java
Intersection of two list of different object based on common key - Java 8
private List<User> intersection(List<User> users, List<OtherUser> list) {
return list.stream()
.flatMap(OtherUser -> users.stream()
.filter(user -> user.getId()
.equalsIgnoreCase(OtherUser.getId())))
.collect(Collectors.toList());
}
Solution 17 - Java
public static <T> Set<T> intersectCollections(Collection<T> col1, Collection<T> col2) {
Set<T> set1, set2;
if (col1 instanceof Set) {
set1 = (Set) col1;
} else {
set1 = new HashSet<>(col1);
}
if (col2 instanceof Set) {
set2 = (Set) col2;
} else {
set2 = new HashSet<>(col2);
}
Set<T> intersection = new HashSet<>(Math.min(set1.size(), set2.size()));
for (T t : set1) {
if (set2.contains(t)) {
intersection.add(t);
}
}
return intersection;
}
JDK8+ (Probably Best Performance)
public static <T> Set<T> intersectCollections(Collection<T> col1, Collection<T> col2) {
boolean isCol1Larger = col1.size() > col2.size();
Set<T> largerSet;
Collection<T> smallerCol;
if (isCol1Larger) {
if (col1 instanceof Set) {
largerSet = (Set<T>) col1;
} else {
largerSet = new HashSet<>(col1);
}
smallerCol = col2;
} else {
if (col2 instanceof Set) {
largerSet = (Set<T>) col2;
} else {
largerSet = new HashSet<>(col2);
}
smallerCol = col1;
}
return smallerCol.stream()
.filter(largerSet::contains)
.collect(Collectors.toSet());
}
If you don't care about performance and prefer smaller code just use:
col1.stream().filter(col2::contains).collect(Collectors.toList());
Solution 18 - Java
First, I am copying all values of arrays into a single array then I am removing duplicates values into the array. Line 12, explaining if same number occur more than time then put some extra garbage value into "j" position. At the end, traverse from start-end and check if same garbage value occur then discard.
public class Union {
public static void main(String[] args){
int arr1[]={1,3,3,2,4,2,3,3,5,2,1,99};
int arr2[]={1,3,2,1,3,2,4,6,3,4};
int arr3[]=new int[arr1.length+arr2.length];
for(int i=0;i<arr1.length;i++)
arr3[i]=arr1[i];
for(int i=0;i<arr2.length;i++)
arr3[arr1.length+i]=arr2[i];
System.out.println(Arrays.toString(arr3));
for(int i=0;i<arr3.length;i++)
{
for(int j=i+1;j<arr3.length;j++)
{
if(arr3[i]==arr3[j])
arr3[j]=99999999; //line 12
}
}
for(int i=0;i<arr3.length;i++)
{
if(arr3[i]!=99999999)
System.out.print(arr3[i]+" ");
}
}
}
Solution 19 - Java
After testing, here is my best intersection approach.
Faster speed compared to pure HashSet Approach. HashSet and HashMap below has similar performance for arrays with more than 1 million records.
As for Java 8 Stream approach, speed is quite slow for array size larger then 10k.
Hope this can help.
public static List<String> hashMapIntersection(List<String> target, List<String> support) {
List<String> r = new ArrayList<String>();
Map<String, Integer> map = new HashMap<String, Integer>();
for (String s : support) {
map.put(s, 0);
}
for (String s : target) {
if (map.containsKey(s)) {
r.add(s);
}
}
return r;
}
public static List<String> hashSetIntersection(List<String> a, List<String> b) {
Long start = System.currentTimeMillis();
List<String> r = new ArrayList<String>();
Set<String> set = new HashSet<String>(b);
for (String s : a) {
if (set.contains(s)) {
r.add(s);
}
}
print("intersection:" + r.size() + "-" + String.valueOf(System.currentTimeMillis() - start));
return r;
}
public static void union(List<String> a, List<String> b) {
Long start = System.currentTimeMillis();
Set<String> r= new HashSet<String>(a);
r.addAll(b);
print("union:" + r.size() + "-" + String.valueOf(System.currentTimeMillis() - start));
}
Solution 20 - Java
retainAll() method use for finding common element..i.e;intersection list1.retainAll(list2)
Solution 21 - Java
You can use the methods:
CollectionUtils.containsAny
and CollectionUtils.containsAll
from Apache Commons.
Solution 22 - Java
If you had your data in Sets you could use Guava's Sets
class.
Solution 23 - Java
Final solution:
//all sorted items from both
public <T> List<T> getListReunion(List<T> list1, List<T> list2) {
Set<T> set = new HashSet<T>();
set.addAll(list1);
set.addAll(list2);
return new ArrayList<T>(set);
}
//common items from both
public <T> List<T> getListIntersection(List<T> list1, List<T> list2) {
list1.retainAll(list2);
return list1;
}
//common items from list1 not present in list2
public <T> List<T> getListDifference(List<T> list1, List<T> list2) {
list1.removeAll(list2);
return list1;
}
Solution 24 - Java
If the number matches than I am checking it's occur first time or not with help of "indexOf()" if the number matches first time then print and save into in a string so, that when the next time same number matches then it's won't print because due to "indexOf()" condition will be false.
class Intersection
{
public static void main(String[] args)
{
String s="";
int[] array1 = {1, 2, 5, 5, 8, 9, 7,2,3512451,4,4,5 ,10};
int[] array2 = {1, 0, 6, 15, 6, 5,4, 1,7, 0,5,4,5,2,3,8,5,3512451};
for (int i = 0; i < array1.length; i++)
{
for (int j = 0; j < array2.length; j++)
{
char c=(char)(array1[i]);
if(array1[i] == (array2[j])&&s.indexOf(c)==-1)
{
System.out.println("Common element is : "+(array1[i]));
s+=c;
}
}
}
}
}