Tối đa hoá mảng từ 2 mảng cho trước

Cho 2 mảng số nguyên A và B đều có size là N (N > 0). Viết chương trình trả về một mảng có size N mà các phần tử trong mảng là các phần tử lớn nhất từ 2 mảng A và B.

Ví dụ

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

Các phần tử 5, 6, 4 là các phần tử lớn nhất được chọn từ 2 mảng A và B

Nếu các bạn đang nghĩ đến việc dùng vòng lặp duyệt thì có vẽ là cách này khá rủi ro đấy. Mình sẽ đề xuất là sắp xếp trước nhé.

Sau khi 2 mảng A và B được sắp xếp thì chúng ta lần lượt so sánh từng cặp một của 2 mảng và chọn ra những phần tử lớn nhất cho vào kết quả.

Các bước làm

B1: Sắp xếp A và B

B2: Khởi tạo index_a = n, index_b = n, index = 0, R[n]

B3: Duyệt trong khi index < n

if(A[index_a] >= B[index_b]
1. R[index] = A[index_a]
2. index_a–
else
1. R[index_a] = B[index_b]
2. index_b–
index++

import java.util.Arrays;

public class Main {

    public static int[] maximizeArray(int[] A, int[] B, int n) {
        int[] R = new int[n];
        Arrays.sort(A);
        Arrays.sort(B);
        int index_a = n - 1, index_b = n - 1, index = 0;
        while (index < n) {
            if (A[index_a] >= B[index_b]) {
                R[index] = A[index_a];
                index_a--;
            } else {
                R[index] = B[index_b];
                index_b--;
            }
            index++;
        }
        return R;
    }
    public static void main(String[] args) {
        int A[] = {2, 4, 3};
        int B[] = {5, 6, 1};
        int[] R = maximizeArray(A, B, A.length);
        for (int e : R)
            System.out.print(e + " ");

    }
}

Output: 6 5 4

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

Linh đề bài: https://www.geeksforgeeks.org/maximize-elements-using-another-array/