Menu
I have two sets from Guava HashMultimap.values().
I need to find out if there's an intersection of these two non-empty sets with the best possible time complexity.
I don't need to know about the common elements, just if there's at least one common element.
I was thinking of using Sets.intersection(), but it has time complexity O(m+n). Can we find out whether there's a common element without creating the entire intersection?
Something like (pseudocode):
set.intersection(set2).any()
The data set is pretty big and this operation happens within a loop, and hence performance is paramount.
659
Use the intersection function to check if both sets have any elements in common. If they have many elements in common, then print the intersection of both sets.
The disjoint() method of Java Collections class is used to check whether two specified collections are disjoint or not. It returns true if the two specified collections have no elements in common.
pick 2 item from list1 to search, search in list2 up to , either the list exhausts or matching element is found , if element is found search in list3 other wise pick the 3 item from list1 i.e 5 to search. Save this answer.
With the normal JDK, this is just
!Collections.disjoint(set1, set2)
This bails immediately if an element is found in common.
(Although -- for what it's worth -- Sets.intersection is lazier than you realize. It returns a view in constant time, and its isEmpty() method would also bail immediately upon finding the first element in common, so it'd be just as efficient.)
158
You may use Collection#retainAll().
Retains only the elements in this collection that are contained in the specified collection (optional operation). In other words, removes from this collection all of its elements that are not contained in the specified collection.
4
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
