Find indices of common elements in arraylists in java
I have multiple ArrayLists with no repeated items. I want to find their intersection and return the indices of the common elements in each arraylist.
For example, if I have an input like {0,1,2},{3,0,4},{5,6,0}
, then I want to return {0},{1},{2}
ie the indices of the generic element 0 here.
One way I can think of is to use succesive retainAll()
for all ArrayLists to get the intersection and then find the indices of the intersection elements using indexOf()
the ArrayList for each input array.
Is there a better way to do this?
source to share
It will take at least a O(nlogn)
while to sort the list first . If you are looking for a more efficient algorithm, you can get O(n)
using hashmaps.
For example,
A=[0,1,2],B=[3,0,4],C=[5,6,0]
You can loop through each list and add items with a hash for the item. The final hash will look like
H = {0:[0,1,2], 1:[1], 2:[2], 3:[0], 4:[2], 5:[0], 6:[1]}
Here the key is the item and the value is the index in the corresponding list. Now just loop the hashmap to find lists that are of size 3, in this case to get the indices.
The code will look something like this (untested):
int[][] lists = {{0,1,2}, {3,0,4}, {5,6,0}};
// Create the hashmap
Map<Integer, List<Integer>> H = new HashMap<Integer, List<Integer>>();
for(int i = 0; i < lists.length; i++){
for(int j = 0; j < lists[0].length; j++){
// create the list if this is the first occurance
if(!H.containsKey(lists[i][j]))
H.put(lists[i][j], new ArrayList<Integer>());
// add the index to the list
H.get(lists[i][j]).add(j);
}
}
// Print out indexes for elements that are shared between all lists
for(Map.Entry<Integer, List<Integer>> e : H.entrySet()){
// check that the list of indexes matches the # of lists
if(e.getValue().size() == lists.length){
System.out.println(e.getKey() + ":" + e.getValue());
}
}
EDIT: Just noticed that you suggested using keepAll () in your question. It would also be O (n).
source to share
Here's a very inefficient but readable solution using streams that return a list of lists to you.
int source[][];
Arrays.stream(source)
.map(list -> IntMap.range(0, list.length)
.filter(i -> Arrays.stream(source)
.allMatch(l -> Arrays.binarySearch(l, list[i]) >= 0))
.collect(Collectors.toList()))
.collect(Collectors.toList());
You can add calls to toArray to convert to arrays if needed.
source to share