รวม k อาร์เรย์ที่จัดเรียงแล้วใน Java

ภาพรวมปัญหา

ได้รับ n อาร์เรย์จำนวนเต็มที่จัดเรียงแล้ว ต้องรวมเป็นอาร์เรย์เดียวที่จัดเรียงในรันไทม์

ตัวอย่าง

ตัวอย่างที่ 1

Input: a[] = {21,22,23,24}, b[] = {28,31,35}

Output: {21,22,23,24,28,31,35}

ตัวอย่างที่ 2

Input: a[] = {1,3,5,7,9,11,13}, b[] = {14,16,18}, c[] = {19,20,21,22}

Output: {1,3,5,7,9,11,13,14,16,18,19,20,21,22}

แนวทางการแก้ปัญหา

• ใช้ PriorityQueue เก็บออบเจกต์ ArrayBucket (อาร์เรย์และดัชนีปัจจุบัน)
• ArrayBucket implements Comparable เปรียบเทียบค่าที่ดัชนีปัจจุบัน
• เริ่มต้นใส่ตัวแรกของทุกอาร์เรย์เข้า Queue
• นำค่าน้อยที่สุดออก เก็บในผลลัพธ์ แล้วใส่ตัวถัดไปของอาร์เรย์เดิมเข้า Queue
• ทำซ้ำจน Queue ว่าง

ตัวอย่างโค้ด Java

import java.util.*;

class ArrayBucket implements Comparable {
    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 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));
    }
}

ผลลัพธ์

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