3 정렬된 배열의 공통 요소

오름차순으로 정렬된 3개의 배열이 주어집니다. 세 배열 모두에서 공통적인 요소를 찾으십시오.
참고: 추가 데이터 구조를 사용하지 않고 중복을 처리할 수 있습니까?

예 1:
입력:
n1 = 6; A = {1, 5, 10, 20, 40, 80}
n2 = 5; B = {6, 7, 20, 80, 100}
n3 = 8; C = {3, 4, 15, 20, 30, 70, 80, 120}
출력: 20 80
_설명: 20과 80은 유일한
A, B 및 C의 공통 요소.
_
예 2:
입력:
_n1=3; A={3, 3, 3}
n2=3; B={3, 3, 3}
n3=3; C={3, 3, 3}
_출력: 3

이 질문은 MAQ Software, Microsoft, VMWare와 같은 회사에서 제기되었습니다.

이 질문을 해결하려면 여기를 클릭하십시오:( https://practice.geeksforgeeks.org/problems/common-elements1132/1# )

접근 방식 1:
시간 복잡도: O(n1+n2+n3)
공간 복잡도: O(1)
여기에서 우리는 3개의 정렬된 배열을 반복하기 위해 3개의 포인터 i, j, k를 사용했습니다.

import java.util.*;

public class commonEle_in_3sorted {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter n1: ");
        int n1 = sc.nextInt();
        System.out.print("Enter n2: ");
        int n2 = sc.nextInt();
        System.out.print("Enter n3: ");
        int n3 = sc.nextInt();
        int[] A = new int[n1];
        int[] B = new int[n2];
        int[] C = new int[n3];
        System.out.println("Enter the elements of the array A: ");
        for (int i = 0; i < n1; i++) {
            A[i] = sc.nextInt();
        }
        System.out.println("Enter the elements of the array B: ");
        for (int i = 0; i < n2; i++) {
            B[i] = sc.nextInt();
        }
        System.out.println("Enter the elements of the array C: ");
        for (int i = 0; i < n3; i++) {
            C[i] = sc.nextInt();
        }
        M1commonElement(A, B, C, n1, n2, n3);
    }

    public static void M1commonElement(int A[], int B[], int C[], int n1, int n2, int n3) {
        int i = 0, j = 0, k = 0;
        ArrayList<Integer> al = new ArrayList<>();
        while (i < n1 && j < n2 && k < n3) {
            if (A[i] == B[j] && A[i] == C[k]) {
                al.add(A[i]);// common element
                int ele = A[i];
                // to remove duplicacy
                while (i<n1 && A[i]==ele)
                    i++;
                while (j<n2 && B[j] == ele)
                    j++;
                while (k<n3 && C[k] == ele)
                    k++;
            } 
            else if (A[i] < B[j])
                i++;
            else if (B[j] < C[k])
                j++;
            else
                k++;

        }
        for (int ele : al) {
            System.out.println(ele);
        }
    }

접근 방식 2:
시간 복잡도: O(n1+n2+n3)
공간 복잡도: O(n1+n2+n3)
여기에서 HashMap을 사용하여 3개의 정렬된 배열을 저장합니다. 그런 다음 루프를 다시 반복하고 해당 요소가 HashMap( hm1 , hm2 , hm3 )에 있는지 확인했습니다.

 public static void M2commonElement(int A[], int B[], int C[], int n1, int n2, int n3) {
        HashMap<Integer, Integer> hm1 = new HashMap<>();
        HashMap<Integer, Integer> hm2 = new HashMap<>();
        HashMap<Integer, Integer> hm3 = new HashMap<>();
        for (int i = 0; i < n1; i++)
            hm1.put(A[i], i);
        for (int i = 0; i < n2; i++)
            hm2.put(B[i], i);
        for (int i = 0; i < n3; i++)
            hm3.put(C[i], i);

        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < n1; i++) {
            if (hm1.containsKey(A[i]) && hm2.containsKey(A[i]) && hm3.containsKey(A[i])) {
                arr.add(A[i]);
                hm1.remove(A[i]);
            }
        }
        for (int ele : arr)
            System.out.print(arr);
    }