我有這種方法可以將 2 個排序陣列合并為一個排序陣列：
public void merge(T[] a, int l1, int r1, T[] b, int l2, int r2, T[] c, int l3) {
while (l1 < r1 && l2 < r2) {
if (a[l1].compareTo(b[l2]) < 0) {
c[l3 ] = a[l1 ];
} else
c[l3 ] = b[l2 ];
}
while (l1 < r1)
c[l3 ] = a[l1 ];
while (l2 < r2)
c[l3 ] = b[l2 ];
}
但現在我想一次用4 陣列來做。
我嘗試了很長時間才想出一個解決方案，但并沒有真正成功。有人知道怎么做嗎？
uj5u.com熱心網友回復：
使用 Java8 流有一種比手動操作更簡單的方法：
- 將所有陣列合并為一個流（我使用了 2 個，但您可以使用任意多個）：
int[] arr1 = {1, 7, 10};
int[] arr2 = {1, 2, 4, 9};
Stream<int[]> ints = Stream.of(arr1, arr2);
- 然后
flatMap他們sort在一個流中：
IntStream intStream = ints.flatMapToInt(Arrays::stream).sorted();
當你列印它們時，你會看到所有的數字排序：
intStream.forEach(System.out::println);
1
1
2
4
7
9
10
結合在一個函式中，它可能看起來像這樣：
public int[] merge(int[]... arrays) {
return Stream.of(arrays)
.flatMapToInt(Arrays::stream)
.sorted()
.toArray();
}
編輯：流的優點是，您可以根據需要進一步修改值。例如，通過利用該distinct功能，您可以輕松洗掉重復項：
intStream = intStream.distinct();
intStream.forEach(System.out::println);
1
2
4
7
9
10
uj5u.com熱心網友回復：
下面是如何合并任意數量的排序陣列的描述：
- 消除空陣列；
- 找到元素的總數并基于它創建一個結果陣列；
- 定義一個陣列，該陣列將在每個源陣列中保持當前位置；
- 對結果陣列中的每個位置使用嵌套
for回圈選擇所有當前可訪問值的最小值。
實作可能如下所示：
public static int[] mergeNSorted(int[]... arrays) {
int[][] normalized = getNormalized(arrays);
int[] result = new int[getTotalLength(normalized)];
int[] positions = new int[normalized.length]; // position for each array
for (int pos = 0; pos < result.length; pos ) {
int minCurVal = Integer.MAX_VALUE;
int curArr = 0;
for (int i = 0; i < normalized.length; i ) {
if (positions[i] < normalized[i].length && normalized[i][positions[i]] < minCurVal) {
minCurVal = normalized[i][positions[i]];
curArr = i;
}
}
result[pos] = minCurVal;
positions[curArr] ;
}
return result;
}
public static int[][] getNormalized(int[]... arrays) {
return Arrays.stream(arrays)
.filter(arr -> arr.length != 0)
.toArray(int[][]::new);
}
public static int getTotalLength(int[]... arrays) {
long totalLen = 0;
for (int[] arr : arrays) totalLen = arr.length;
if (totalLen > Integer.MAX_VALUE) throw new IllegalArgumentException("total length exceeded Integer.MAX_VALUE");
return (int) totalLen;
}
main()- 演示
public static void main(String[] args) {
int[][] input =
{{1, 3}, {}, {2, 6, 7}, {10}, {4, 5, 8, 9}};
System.out.println(Arrays.toString(mergeNSorted(input)));
}
輸出
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
uj5u.com熱心網友回復：
我不是 Java 程式員，所以我只會給出 Pythonesque 偽代碼。
首先將每個非空陣列變成一個三元組：
(next_value, index, array)
現在將它們放入按下一個值排序的優先級佇列中。
while 0 < queue.size():
(next_value, index, array) = queue.poll()
answer.append(next_value)
if index 1 < array.length:
queue.add((array[index 1], index 1, array))
如果您有k陣列，這將對O(log(k))每個生成的元素進行比較。
可悲的是，Java 似乎沒有任何與該swaptop方法相對應的東西。我練習如果一個陣列有一系列值，.peek()用于獲取頂部元素，那么.swaptop(...)如果可以的話，讓你通過O(1)每個元素的作業來完成這些運行。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/471909.html
上一篇：如何按升序對目錄串列進行排序？