I have 3 arrays

int a[] = {1,3,7,6};
int b[] = {2,5,0,4};
int c[] = {11,23,71,6};

I want to find common elements from these three arrays optimaly. I am thinking to use 3 for loops to find common elements but this is not optimal .So is there any optimal better way of doing it rather than using nested for loop?

CodePudding user response：

This is the most concise solution, though I am not sure it is the most efficiant:

List<Integer> commonItems = new ArrayList<>(Arrays.asList(a));
commonItems.retainAll(Arrays.asList(b));
commonItems.retainAll(Arrays.asList(c));

JDK doc of List.retainAll:

Retains only the elements in this list that are contained in the specified collection (optional operation). In other words, removes from this list all of its elements that are not contained in the specified collection.

CodePudding user response：

You can use a Set for each array to store elements so that they can be accessed in O(1) time and then iterate over elements in any set and check if it's present in other two sets as well since set of common elements is guaranteed to be a subset of all the three sets.

    int a[] = {1,3,7,6};
    int b[] = {2,5,0,4};
    int c[] = {11,23,71,6};
    Set<Integer> set1 = new HashSet<>();
    Set<Integer> set2 = new HashSet<>();
    Set<Integer> set3 = new HashSet<>();
    for(int x: a)
        set1.add(x);
    for(int x: b)
        set2.add(x);
    for(int x: c)
        set3.add(x);
    List<Integer> res = new ArrayList<>();
    Iterator<Integer> itr = set1.iterator();
    while(itr.hasNext()){
        int ele = itr.next();
        if(set2.contains(ele) && set3.contains(ele)){
            res.add(ele);
        }
    }
    return res;

This approach should also work in cases where an element is repeated in an array and thus can increase frequency of count if single hashmap based approach is used.

CodePudding user response：

Assuming the arrays are having unique elements in themself (no duplicates in an array)

You can use some data structure like HashMap to push all elements of the arrays as keys, and values as their count of occurrences to find common elements if the value is 3 :

private ArrayList<Integer> commonElements() {
        int a[] = {1,3,7,6};
        int b[] = {2,5,0,4};
        int c[] = {11,23,71,6};
        
        HashMap<Integer, Integer> elementCunt = new HashMap<>();
        
        for(int element: a) {
            if(elementCunt.containsKey(element)) {
                elementCunt.put(element, elementCunt.get(element)   1);
            } else {
                elementCunt.put(element, 1);
            }
        }
        
        for(int element: b) {
            if(elementCunt.containsKey(element)) {
                elementCunt.put(element, elementCunt.get(element)   1);
            } else {
                elementCunt.put(element, 1);
            }
        }
        
        for(int element: c) {
            if(elementCunt.containsKey(element)) {
                elementCunt.put(element, elementCunt.get(element)   1);
            } else {
                elementCunt.put(element, 1);
            }
        }
        
        Iterator<Integer> itr = elementCunt.keySet().iterator();
        
        ArrayList<Integer> commonElements = new ArrayList<>();
        
        while(itr.hasNext()) {
            int key = itr.next();
            if(elementCunt.get(key) == 3) {
                commonElements.add(key);
            }
        }
        
        return commonElements;
    }

CodePudding user response：

Well, you can use n number of different hash-map like data structures for n number of arrays. Filter out only distinct elements from array to hash-map. And, at the end, get common elements from all n hash-maps.

This will reduce your complexity to o(n m) where n is the number of hash-maps (or arrays) used and m- is the size of each array.

Code:

public class CommonElems {
    public static void main(String[] args) {
        int a[] = {1,3,7,6};
        int b[] = {2,5,0,4,6};
        int c[] = {11,23,71,6};
        
        Map<Integer, Integer> mapA = getUniqueElements(a);
        Map<Integer, Integer> mapB = getUniqueElements(b);
        Map<Integer, Integer> mapC = getUniqueElements(c);
        
        List<Integer> resultset = new ArrayList<>();
        for(Map.Entry<Integer, Integer> m : mapA.entrySet()) {
            if(mapB.containsKey(m.getKey()) && mapC.containsKey(m.getKey())) {
                resultset.add(m.getKey());
            }
        }
        System.out.println(resultset);
    }

    private static Map<Integer, Integer> getUniqueElements(int[] a) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i : a) {
            if(!map.containsKey(i)) {
                map.put(i, 1);
            }
        }
        return map;
    }
}