Find all numbers that appear in each set of lists
I have multiple ArrayLists Integer objects stored in a HashMap.
I want to get a list (ArrayList) of all numbers (Integer objects) that appear in each list.
My thinking so far:
- Iterate through each ArrayList and put all values into a HashSet
- This will give us a "list" of all the values in the lists, but only once
- Iterating Through HashSet
2.1 With each iteration, execute ArrayList.contains ()
2.2 If none of the ArrayLists return false for the operation, add a number to the "master list" that contains all the final values.
If you can think of something faster or more efficient, funny since I wrote this, I came up with a pretty good solution. But I will post it anyway just in case it is useful to someone else.
But of course, if you have a better way, let me know.
a source to share
I'm not sure I understand your purpose. But if you want to find the intersection of a collection of List <Integer> objects, you can do the following:
public static List<Integer> intersection(Collection<List<Integer>> lists){
if (lists.size()==0)
return Collections.emptyList();
Iterator<List<Integer>> it = lists.iterator();
HashSet<Integer> resSet = new HashSet<Integer>(it.next());
while (it.hasNext())
resSet.retainAll(new HashSet<Integer>(it.next()));
return new ArrayList<Integer>(resSet);
}
This code runs in linear time on a total cardinality. This is actually the linear time average , due to the use of the HashSet.
Also note that if you use ArrayList.contains () in a loop, this can lead to quadratic complexity, since this method works in linear time, unlike HashSet.contains (), which runs in constant time.
a source to share
You need to change step 1: - Use the shortest list instead of your hashSet (if it is not in the shortest list, it is not in all lists ...)
Then the call contains in other lists and removes the value as soon as one returns false (and skip additional tests for that value)
At the end, the shortest list will contain the answer ...
some code:
public class TestLists {
private static List<List<Integer>> listOfLists = new ArrayList<List<Integer>>();
private static List<Integer> filter(List<List<Integer>> listOfLists) {
// find the shortest list
List<Integer> shortestList = null;
for (List<Integer> list : listOfLists) {
if (shortestList == null || list.size() < shortestList.size()) {
shortestList = list;
}
}
// create result list from the shortest list
final List<Integer> result = new LinkedList<Integer>(shortestList);
// remove elements not present in all list from the result list
for (Integer valueToTest : shortestList) {
for (List<Integer> list : listOfLists) {
// no need to compare to itself
if (shortestList == list) {
continue;
}
// if one list doesn't contain value, remove from result and break loop
if (!list.contains(valueToTest)) {
result.remove(valueToTest);
break;
}
}
}
return result;
}
public static void main(String[] args) {
List<Integer> l1 = new ArrayList<Integer>(){{
add(100);
add(200);
}};
List<Integer> l2 = new ArrayList<Integer>(){{
add(100);
add(200);
add(300);
}};
List<Integer> l3 = new ArrayList<Integer>(){{
add(100);
add(200);
add(300);
}};
List<Integer> l4 = new ArrayList<Integer>(){{
add(100);
add(200);
add(300);
}};
List<Integer> l5 = new ArrayList<Integer>(){{
add(100);
add(200);
add(300);
}};
listOfLists.add(l1);
listOfLists.add(l2);
listOfLists.add(l3);
listOfLists.add(l4);
listOfLists.add(l5);
System.out.println(filter(listOfLists));
}
}
a source to share
- Create
Set
(for exampleHashSet
) from the firstList
. - For each remaining list:
- challenge
set.retainAll (list)
if bothList
andSet
are small enough - otherwise call
set.retainAll (new HashSet <Integer> (list))
- challenge
I cannot say after what thresholds the second option of step 2 becomes faster, but I think, perhaps > 20
by size or so. If your lists are small, you can't bother with this check.
As I recall, Apache Collections has better integer structures if you care not only about the O (*) part but also the factor.
a source to share
Using Google Multiset Collections makes this (view) wise (although I also like Eyal's answer ). It's probably not as time / memory efficient as some of the others here, but it's very clear what's going on.
Assuming the lists do not contain duplicates within themselves:
Multiset<Integer> counter = HashMultiset.create();
int totalLists = 0;
// for each of your ArrayLists
{
counter.addAll(list);
totalLists++;
}
List<Integer> inAll = Lists.newArrayList();
for (Integer candidate : counter.elementSet())
if (counter.count(candidate) == totalLists) inAll.add(candidate);`
if the lists can contain duplicate elements, they can be passed through the set first:
counter.addAll(list) => counter.addAll(Sets.newHashSet(list))
Finally, this is also ideal if you want, perhaps want to later retrieve some additional data (for example, how close any particular value was to make a cut).
Another approach that slightly modifies Eyal (basically collapsing the filtering action of the list through the set and then keeping all the overlapping elements) and lighter than above:
public List<Integer> intersection(Iterable<List<Integer>> lists) {
Iterator<List<Integer>> listsIter = lists.iterator();
if (!listsIter.hasNext()) return Collections.emptyList();
Set<Integer> bag = new HashSet<Integer>(listsIter.next());
while (listsIter.hasNext() && !bag.isEmpty()) {
Iterator<Integer> itemIter = listsIter.next().iterator();
Set<Integer> holder = new HashSet<Integer>(); //perhaps also pre-size it to the bag size
Integer held;
while (itemIter.hasNext() && !bag.isEmpty())
if ( bag.remove(held = itemIter.next()) )
holder.add(held);
bag = holder;
}
return new ArrayList<Integer>(bag);
}
a source to share