在Java中合并k个排序数组

  • Z时代
  • 2024-01-10
  • 分类：综合

给定了“n”个数组，假设我们采用三个数组，即整数类型的 arr1[]、arr2[] 和 arr3[]。任务是以这样一种方式合并所有给定的整数数组，即结果数组仅在运行时排序。

让我们用例子来理解

输入 -

整数

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

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

输出 -int 结果[]={21,22,23,24,28,31,35}。

说明 - 数组元素在添加之前进行比较，并根据它们在结果数组中的合适位置进行添加。

输入 -

整数

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[] 以及一个结果数组作为 result[] 并将其设置为对方法的调用作为 mergeSortedArray(new int[][] { arr1, arr2, arr3 })

  • 方法内部 mergeSortedArray(new int[][] { arr1, arr2, arr3 })

    • 创建一个变量作为priority queue类型的队列和一个变量作为total并将其设置为0。

    • 从 i 到 0 开始循环 FOR，直到数组的长度，并将数组桶中的元素添加到声明为队列的变量中，并将 total 设置为 total + arr[i].length。

    • 将 m 设置为 0 并声明 result[] 整数数组。

    • 开始 while = false 然后将 ArrayBucket ac设置为, + 1))queue.isEmpty()queue.poll()ac.index

    • 返回结果

示例

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]

以上是 在Java中合并k个排序数组 的全部内容， 来源链接： utcz.com/z/347500.html

回到顶部