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

Chúng ta được cho một số mảng là ‘n’, giả sử chúng ta lấy ba mảng, tức là arr1 [], arr2 [] và arr3 [] kiểu số nguyên. Nhiệm vụ là hợp nhất tất cả các mảng số nguyên đã cho theo cách sao cho mảng kết quả chỉ được sắp xếp trong thời gian chạy.

Hãy cho chúng tôi hiểu với ví dụ

Đầu vào -

Int

a [] ={21,22,23,24};

int b [] ={28,31,35}

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

Giải thích - Các phần tử của mảng được so sánh trước khi chúng được thêm và thêm vào theo vị trí thích hợp của chúng trong mảng kết quả.

Đầu vào -

int

a [] ={1,3,5,7,9,11,13};

int b [] ={14,16,18}

int c [] ={19,20,21,22}

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

Giải thích −Các phần tử của mảng được so sánh trước khi chúng được thêm vào và được thêm vào theo vị trí thích hợp của chúng trong mảng kết quả.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

• Nhập ba mảng số nguyên, giả sử arr1 [], arr2 [] và arr3 [] và một mảng kết quả là result [] và đặt nó thành lệnh gọi phương thức là mergeSortedArray (new int [] [] {arr1, arr2, arr3 })

• Bên trong phương thức mergeSortedArray (new int [] [] {arr1, arr2, arr3})

  • Tạo một biến dưới dạng hàng đợi loại ưu tiên và một biến astotal và đặt nó thành 0.

  • Bắt đầu vòng lặp FOR từ i đến 0 cho đến độ dài của một mảng và thêm phần tử từ nhóm của một mảng vào biến được khai báo là hàng đợi và định vị thành tổng + arr [i] .length.

  • Đặt m thành 0 và khai báo mảng số nguyên kết quả [].

  • Bắt đầu trong khi queue.isEmpty () =false sau đó đặt ArrayBucket ac toqueue.poll (), result [m ++] thành ac.arr [ac.index] và kiểm tra IF ac.indexless than ac.arr.length - 1 rồi đặt hàng đợi. thêm (newArrayBucket (ac.arr, ac.index + 1))

  • Trả về kết quả

Ví dụ

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<ArrayBucket>();
      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));
   }
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau

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