জাভাতে Kটি সর্টেড অ্যারে মার্জ করা

আমাদের 'n' সংখ্যক অ্যারে দেওয়া আছে, ধরুন তিনটি অ্যারে arr1[], arr2[] এবং arr3[] ইন্টিজার টাইপের। কাজ হল সব দেয়া ইন্টিজার অ্যারেগুলোকে এমনভাবে মার্জ করা যাতে ফলাফল অ্যারেটি রানটাইমে সর্টেড থাকে।

উদাহরণ দিয়ে বুঝি

উদাহরণ ১

ইনপুট:

int a[] = {21, 22, 23, 24};
int b[] = {28, 31, 35}

আউটপুট: int resultant[] = {21, 22, 23, 24, 28, 31, 35}

ব্যাখ্যা: অ্যারে এলিমেন্টগুলো যোগ করার আগে তুলনা করা হয় এবং ফলাফল অ্যারেতে তাদের উপযুক্ত অবস্থানে যোগ করা হয়।

উদাহরণ ২

ইনপুট:

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

আউটপুট: int resultant[] = {1, 3, 5, 7, 9, 11, 13, 14, 16, 18, 19, 20, 21, 22}

ব্যাখ্যা: অ্যারে এলিমেন্টগুলো যোগ করার আগে তুলনা করা হয় এবং তাদের উপযুক্ত অবস্থানে যোগ করা হয়।

প্রোগ্রামে ব্যবহৃত পদ্ধতি

• তিনটি ইন্টিজার অ্যারে arr1[], arr2[], arr3[] এবং একটি ফলাফল অ্যারে result[] ইনপুট নেওয়া হয় এবং mergeSortedArray(new int[][] { arr1, arr2, arr3 }) মেথড কল করা হয়।
• mergeSortedArray() মেথডের ভিতরে:
  • PriorityQueue টাইপের একটি কিউ এবং total = 0 ভেরিয়েবল ডিক্লেয়ার করা হয়।
  • i=0 থেকে অ্যারের দৈর্ঘ্য পর্যন্ত লুপে প্রতিটি অ্যারের প্রথম এলিমেন্ট কিউতে যোগ করা হয় এবং total += arr[i].length করা হয়।
  • m = 0 এবং result[] ইন্টিজার অ্যারে ডিক্লেয়ার করা হয়।
  • while (!queue.isEmpty()) লুপে:
    • ArrayBucket ac = queue.poll()
    • result[m++] = ac.arr[ac.index]
    • যদি ac.index < ac.arr.length - 1 হয়, তবে queue.add(new ArrayBucket(ac.arr, ac.index + 1))
  • result ফেরত দেওয়া হয়।

উদাহরণ কোড

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

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 = 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]