在 Java 中合并 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(new int[][] { arr1, arr2, arr3 })
创建一个优先级队列类型的变量和一个总变量并将其设置为 0。
开始从 i 到 0 的 FOR 循环,直到数组的长度,并将数组的 bucket 中的元素添加到声明为队列的变量中,并将总设置为 total + arr[i].length。
将 m 设置为 0 并声明 result[] 整数数组。
当queue.isEmpty() = false 时启动,然后将 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))
返回结果
示例
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]