Hợp nhất k mảng đã sắp xếp trong Java

Cho n mảng nguyên (ví dụ 3 mảng arr1[], arr2[], arr3[]). Nhiệm vụ là hợp nhất tất cả thành một mảng kết quả được sắp xếp tại runtime.

Ví dụ minh họa

Đầu vào: a[] = {21,22,23,24}, b[] = {28,31,35}

Đầu ra: resultant[] = {21,22,23,24,28,31,35}

Giải thích: So sánh phần tử trước khi thêm vào vị trí thích hợp.

Đầu vào: a[] = {1,3,5,7,9,11,13}, b[] = {14,16,18}, c[] = {19,20,21,22}

Đầu ra: resultant[] = {1,3,5,7,9,11,13,14,16,18,19,20,21,22}

Phương pháp tiếp cận

• Nhập các mảng, gọi mergeSortedArray(new int[][] {arr1, arr2, arr3})
• Trong mergeSortedArray:
  • Tạo PriorityQueue<ArrayBucket> và biến total = 0
  • Duyệt các mảng, thêm ArrayBucket(arr[i], 0) vào queue, cộng total += arr[i].length
  • Tạo mảng result[total], m = 0
  • While queue không rỗng: poll ArrayBucket ac, result[m++] = ac.arr[ac.index]
  • Nếu ac.index < ac.arr.length-1 thì thêm ArrayBucket(ac.arr, ac.index+1) vào queue
  • Trả về result
• Lớp ArrayBucket implements Comparable<ArrayBucket> so sánh arr[this.index] - o.arr[o.index]

Ví dụ mã Java

import java.util.Arrays;
import java.util.PriorityQueue;

class ArrayBucket implements Comparable<ArrayBucket> {
    int[] arr;
    int index;
    public ArrayBucket(int[] arr, int index) {
        this.arr = arr;
        this.index = index;
    }
    @Override
    public int compareTo(ArrayBucket o) {
        return this.arr[this.index] - o.arr[o.index];
    }
}

public class testClass {
    public static int[] mergeSortedArray(int[][] arr) {
        PriorityQueue<ArrayBucket> queue = new PriorityQueue<>();
        int total = 0;
        for (int i = 0; i < arr.length; i++) {
            queue.add(new ArrayBucket(arr[i], 0));
            total += arr[i].length;
        }
        int m = 0;
        int result[] = new int[total];
        while (!queue.isEmpty()) {
            ArrayBucket ac = queue.poll();
            result[m++] = ac.arr[ac.index];
            if (ac.index < ac.arr.length - 1) {
                queue.add(new ArrayBucket(ac.arr, ac.index + 1));
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        int[] arr1 = { 1, 3, 5, 7 };
        int[] arr2 = { 2, 4, 6, 8 };
        int[] arr3 = { 0, 9, 10, 11 };
        int[] result = mergeSortedArray(new int[][] { arr1, arr2, arr3 });
        System.out.println("The final merged sorted array is :- " + Arrays.toString(result));
    }
}

Đầu ra

The final merged sorted array is :-[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]