Javaでk個のソートされた配列をマージ

「n」個の配列が与えられます。たとえば、整数型のarr1 []、arr2 []、およびarr3[]の3つの配列を使用するとします。タスクは、結果の配列が実行時にのみソートされるように、指定されたすべての整数配列をマージすることです。

例を挙げて理解しましょう

入力 −

Int

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

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

出力 −int result []={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 result []={1,3,5,7,9,11,13,14,16,18,19,20,21,22}。

説明 -配列要素は、追加される前に比較され、結果の配列内の適切な位置に従って追加されます。

以下のプログラムで使用されるアプローチは次のとおりです-

• たとえば、arr1 []、arr2 []、arr3 []の3つの整数配列と、結果の配列をresult []として入力し、mergeSortedArray（new int [] [] {arr1、arr2、arr3 }）

• メソッドmergeSortedArray（new int [] [] {arr1、arr2、arr3}）

  内

  • タイプpriorityqueueのキューとして変数を作成し、変数astotalを作成して、0に設定します。

  • ループFORをiから0まで配列の長さまで開始し、配列のバケットからの要素をキューとして宣言された変数に追加し、total + arr[i].lengthに設定します。

  • mを0に設定し、result[]整数配列を宣言します。

  • queue.isEmpty（）=falseのときに開始し、ArrayBucket ac toqueue.poll（）、result [m++]をac.arr[ac.index]に設定し、ac.indexlessがac.arr.length-1未満の場合にチェックしてからキューを設定します。 add（newArrayBucket（ac.arr、ac.index + 1））

  • 結果を返す

例

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

出力

上記のコードを実行すると、次の出力が生成されます

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