Hợp nhất 2 mảng

Cho 2 mảng số nguyên dương đã được sắp xếp. Mảng thứ nhất A của size m + n, mảng thứ hai B có size n. Biết rằng trong A có n phần tử có giá trị null(Interger.MIN_VALUE). Hãy hợp nhất 2 mảng A và B để có mảng output có m + n phần tử của A và B tăng dần.

Ví dụ:

Input: A[] = {1, null, 5, 7, null, 10, null, 20}, B[] = {8, 13, 25}

Output: R[] = {1, 5, 7, 8, 10, 13, 20, 25}

Cách 1: Hợp 2 mảng lại rồi sắp xếp

Các bước thực hiện:

B1: Khởi tạo mảng R với size m + n, index = 0 B2: Loop A với mỗi phần tử A        if (A[i] != null) thì R[index] = A[i], index++ B3: Loop B với mỗi phần tử B       R[index] = B[i]; index++; B4: Sắp xếp R

 

import java.util.Arrays;

public class Main {

    public static int[] mergeTwoArray(int[] A, int[] B, int m, int n) {
        int[] R = new int[m + n];
        int index = 0;

        // merge A to R
        for (int i = 0; i < m + n; i++)
            if (A[i] != Integer.MIN_VALUE) {
                R[index] = A[i];
                index++;
            }

        // merge B to R
        for (int i = 0; i < n; i++) {
            R[index] = B[i];
            index++;
        }

        // Sort R
        Arrays.sort(R);
        return R;
    }


    public static void main(String[] args) {
        int m = 5, n = 2;
        int[] A = {1, Integer.MIN_VALUE, 5, 7, Integer.MIN_VALUE, 10, Integer.MIN_VALUE, 20};
        int[] B = {8, 13, 25};
        int[] R = mergeTwoArray(A, B, m, n);
        for (int value : R)
            System.out.print(value + " ");
    }
}

Output: R[] = {1, 5, 7, 8, 10, 13, 20, 25}

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

 Cách 2: Sử dụng dữ liệu mảng đã được sắp xếp

Có một vấn đề với cách 1 là chúng ta chưa hề sử dụng dữ kiện mảng được sắp xếp để làm. Mình tin là cái gì đề cho đều phải áp dụng vào thì nó mới tối ưu được.

Các bạn còn nhớ merge sort không? Mình nhớ khúc merge sao khi phân thành các đoạn nhỏ được sắp xếp thì bắt đầu merge các đoạn nhỏ này lại với nhau để được mảng tăng dần.

Mình cũng sẽ xem 2 mảng A và B là 2 mảng nhỏ được sắp xếp và tách ra từ mảng R(kết quả). Việc của chúng ta là thu gọn lại các phần tử từ 2 để thu được kết quả.

Các bước thực hiện

B1: Khởi tạo R[m+n], i, j, k = 0 B2: Trong khi i < m + n && j < m + n       if (A[j] <= B[k] thì R[i] = A[j], j++       else R[i] = B[k], k++       if (R[i] != null) // Interget.MIN_VALUE thì i++ B3: if (k <n) // các phần tử trong B còn lại sau khi kết thúc B2       Thêm các phần tử của B vào R.

 

import java.util.Arrays;

public class Main {

    public static int[] mergeTwoArray(int[] A, int[] B, int m, int n) {
        int[] R = new int[m + n];
        int i = 0, j = 0, k = 0;

        while (i < m + n && j < m + n) {
            if (A[j] <= B[k]) {
                R[i] = A[j];
                j++;
            }
            else {
                R[i] = B[k];
                k++;
            }
            if (R[i] != Integer.MIN_VALUE)
                i++;
        }

        // put all element from B to R
        if (k < n) {
            for(int _i = k; _i < n; _i++) {
                R[i] = B[_i];
                i++;
            }
                }
        return R;
    }


    public static void main(String[] args) {
        int m = 5, n = 3;
        int[] A = {1, Integer.MIN_VALUE, 5, 7, Integer.MIN_VALUE, 10, Integer.MIN_VALUE, 20};
        int[] B = {8, 13, 25};
        int[] R = mergeTwoArray(A, B, m, n);
        for (int value : R)
            System.out.print(value + ", ");
    }
}

Output: R[] = {1, 5, 7, 8, 10, 13, 20, 25}

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

Full source: source

Link đề bài: https://www.geeksforgeeks.org/merge-one-array-of-size-n-into-another-one-of-size-mn/