資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學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 }) 內部
建立一個優先順序佇列型別的變數作為佇列，以及一個變數 total 並將其設定為 0。
從 i 為 0 開始迴圈到陣列長度，並將陣列桶中的元素新增到宣告為佇列的變數中，並將 total 設定為 total + arr[i].length。
將 m 設定為 0 並宣告 result[] 整數陣列。
開始 while 迴圈，當 queue.isEmpty() = false 時，設定 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))
返回 result
示例
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]
629 次瀏覽
