Tìm phần giao của 2 mảng

Cho 2 mảng số nguyên A và có có n và m phần tử. Mỗi phần tử là duy nhất trong 2 mảng A và B. Tìm phần giao của 2 mảng. n, m > 0

Ví dụ

Input: A[] = {1, 3, 5, 7, 8, 2}, B = {3, 4, 0, 2}
Output: 3, 2

Cách 1: Sử dụng vòng lặp

public class Main {

    public static void printUnion(int[] A, int[] B, int n, int m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (A[i] == B[j])
                    System.out.print(A[i] + " ");
            }
        }
    }
    public static void main(String[] args) {
        int[] A = {1, 3, 5, 7, 8, 2};
        int[] B = {3, 4, 0 , 2};
        printUnion(A, B, A.length, B.length);
    }
}

Output: 3, 2

Độ phức tạp: O(n²)

Cách 2: Sắp xếp

import java.util.Arrays;

public class Main {

    public static void printUnionSort(int[] A, int[] B, int n, int m) {
        Arrays.sort(A);
        Arrays.sort(B);

        int index_a = 0, index_b = 0;
        while (index_a < n && index_b < m) {
            if (A[index_a] == B[index_b]) {
                System.out.print(A[index_a] + " ");
                index_a++; index_b++;
            } else if (A[index_a] > A[index_b])
                index_b++;
            else index_a++;
        }
    }

    public static void main(String[] args) {
        int[] A = {1, 3, 5, 7, 8, 2};
        int[] B = {3, 4, 0, 2};
        printUnionSort(A, B, A.length, B.length);
    }
}

Output: 2, 3

Độ phức tạp: O(nlogn)

Link đề bài: https://www.geeksforgeeks.org/union-and-intersection-of-two-sorted-arrays-2/