ผสาน k sorted arrays ใน Java

เราได้รับอาร์เรย์จำนวน 'n' สมมติว่าเราใช้อาร์เรย์สามชนิด ได้แก่ arr1[], arr2[] และ arr3[] ของประเภทจำนวนเต็ม งานคือการผสานอาร์เรย์จำนวนเต็มที่กำหนดทั้งหมดในลักษณะที่อาร์เรย์ผลลัพธ์ถูกจัดเรียงในรันไทม์เท่านั้น

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล −

Int

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

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

ผลผลิต ผลลัพธ์ผลลัพธ์[ ]={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 ผลลัพธ์[ ]={1,3,5,7,9,11,13,14,16,18,19,20,21,22}.

คำอธิบาย −องค์ประกอบอาร์เรย์จะถูกเปรียบเทียบก่อนที่จะเพิ่มและเพิ่มตามตำแหน่งที่เหมาะสมในอาร์เรย์ผลลัพธ์

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

• ป้อนอาร์เรย์จำนวนเต็มสามชุด สมมติว่า arr1[], arr2[] และ arr3[] และอาร์เรย์ผลลัพธ์เป็นผลลัพธ์[] และตั้งค่าให้เรียกใช้เมธอดเป็น mergeSortedArray(new int[][] { arr1, arr2, arr3 })

• ภายในเมธอด mergeSortedArray(new int[][] { arr1, arr2, arr3 })

  • สร้างตัวแปรเป็นคิวของลำดับความสำคัญของประเภทและตัวแปร astotal และตั้งค่าเป็น 0

  • เริ่มการวนซ้ำ FOR จาก i ถึง 0 จนถึงความยาวของอาร์เรย์และเพิ่มองค์ประกอบจากที่เก็บข้อมูลของอาร์เรย์ไปยังตัวแปรที่ประกาศเป็นคิวและเซ็ตโตทอลเป็นยอดรวม + arr[i].length.

  • ตั้งค่า m เป็น 0 และประกาศผลลัพธ์[] integer array.

  • เริ่มในขณะที่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]