Tìm phần hợp 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 hợp của 2 mảng và in ra mảng kết quả R đã được sắp xếp, các phần tử trong R phải là duy nhất. n, m > 0

Ví dụ

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

Cách 1: Vòng lặp

Các bước làm

B1: Khởi tạo mảng R[m + n], index = 0 B2: Loop mảng A, với mỗi phần tử trong A nếu chưa có trong R thì thêm vào R B3: Tương tự B2 để thực hiện với B B4: Sắp xếp mảng

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main {

    public static void printIntersect(int[] A, int[] B, int n, int m) {
        int[] R = new int[n + m];
        int index = 0;
        // Lấy những phần tử trong A mà chưa có trong R
        for (int i = 0; i < n; i++) {
            if (!isPresent(R, index, A[i])) {
                R[index] = A[i];
                index++;
            }
        }

        // Lấy những phần tử trong B  mà chưa có trong R
        for (int i = 0; i < m; i++) {
            if (!isPresent(R, index, B[i])) {
                R[index] = B[i];
                index++;
            }
        }

        // Sắp xếp mảng
        Arrays.sort(R, 0, index);
        for(int i = 0; i < index; i++){
            System.out.print(R[i] + " ");
        }

    }

    public static boolean isPresent(int[] arr, int n, int x) {
        for (int i = 0; i < n; i++)
            if (arr[i] == x)
                return true;
        return false;
    }

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

Output: 0 1 2 3 4 5 7 8 

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

Cách 2: Sử dụng Set 

Thêm các phần tử của mảng A, B vào Set. Sau đó convert Set sang mảng và sắp xếp mảng.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main {

    public static void printIntersecSet(int[] A, int[] B, int n, int m) {
        Set<Integer> s = new HashSet<>();

        // Thêm tất cả các phần tử vào HashSet
        for (int item : A)
            s.add(item);

        for(int item : B)
            s.add(item);

        // Chuyển HashSet qua mảng số nguyên
        int[] R = new int[s.size()];
        int k = 0;
        for (int item: s)
            R[k++] = item;

        // Sắp xếp mảng
        Arrays.sort(R);

        for(int i = 0; i < s.size(); i++){
            System.out.print(R[i] + " ");
        }
    }

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

Output: 0 1 2 3 4 5 7 8 

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

Link đề: https://www.geeksforgeeks.org/find-union-and-intersection-of-two-unsorted-arrays/