Java 中二維數組的行反轉
一、簡介
在本教程中,我們將了解反轉二維數組的行的問題,並使用內建 Java 庫的一些替代方案來解決該問題。
2. 理解問題
使用二維數組是程式設計師的常見任務。例如,財務電子表格軟體通常被建構為二維數組,其中每個位置代表一個數字或文字。此外,在數位藝術和攝影中,影像通常會儲存為二維數組,其中每個位置代表顏色強度。
操作二維數組時,常見的操作是反轉其所有行。例如,在 Google 試算表中,我們具有按行反轉電子表格的功能。此外,在數位藝術和攝影中,我們可以透過反轉影像的所有行來找到影像的垂直對稱部分。
當我們在 Java 中有一個元素Stream並且想要建立該Stream的反向版本或以相反的順序將其收集到另一個集合中時,就會發生反轉行的其他應用。
問題的定義非常簡單:我們希望二維數組的每一行反轉,以便第一個元素與最後一個元素交換位置,依此類推。換句話說,我們希望將輸入轉換為垂直對稱。值得注意的是,問題與元素的反向自然順序無關,而是與**它們在輸入中出現的相反順序有關。**
3.就地反轉行
為了幫助理解如何就地反轉行,我們可以將二維數組的每一行視為一維數組。因此,一維數組的演算法很簡單:我們只需將目前索引的元素與其對稱索引中的元素交換,直到我們到達中間元素。
例如,該問題的一種解決方案是:
| 原來的 | -5 | 4 | 3 | -2 | 7 |
| 顛倒的 | 7 | -2 | 3 | 4 | -5 |
我們將索引 0 中的元素與 4 交換,將 1 與 3 交換。
因此,如果我們對 2d 數組的每一行調用反向 1d 演算法,那麼我們將求解 2d 情況。
3.1.使用 Java for循環
有了上一節的思路,我們看一下原始碼:
public static void reverseRowsUsingSimpleForLoops(int[][] array) {
for (int row = 0; row < array.length; row++) {
for (int col = 0; col < array[row].length / 2; col++) {
int current = array[row][col];
array[row][col] = array[row][array[row].length - col - 1];
array[row][array[row].length - col - 1] = current;
}
}
}
內部for迴圈解決了一維數組的逆向問題。因此,我們迭代每個元素,將**其與其對稱元素(即列array[row].length – col – 1處的元素)交換,直到到達中間索引。**
外循環呼叫該演算法來反轉輸入的每一行的一維數組。
我們可以使用 JUnit 5 測試和 AssertJ 匹配器驗證結果:
@Test
void givenArray_whenCallReverseRows_thenAllRowsReversed() {
int[][] input = new int[][] { { 1, 2, 3 }, { 3, 2, 1 }, { 2, 1, 3 } };
int[][] expected = new int[][] { { 3, 2, 1 }, { 1, 2, 3 }, { 3, 1, 2 } };
reverseRowsUsingSimpleForLoops(input);
assertThat(input).isEqualTo(expected);
}
3.2.使用巢狀的 Java 8 IntStream
與先前的for迴圈解決方案類似,我們可以使用 Java 8 Streams 來反轉 2d 陣列:
public static void reverseRowsUsingStreams(int[][] array) {
IntStream.range(0, array.length)
.forEach(row -> IntStream.range(0, array[row].length / 2)
.forEach(col -> {
int current = array[row][col];
array[row][col] = array[row][array[row].length - col - 1];
array[row][array[row].length - col - 1] = current;
}));
}
值得注意的是,主要邏輯保持不變——我們交換數組中對稱的元素。
唯一的差異是我們使用IntStream.range()和forEach()的組合來使用索引迭代流。因此,我們可以只交換最裡面的forEach()'s lambda 表達式中的元素。
3.3.使用內建Collections.reverse()方法
我們也可以使用內建的reverse()方法來幫助完成此任務:
public static void reverseRowsUsingCollectionsReverse(int[][] array) {
for (int row = 0; row < array.length; row++) {
List <Integer> collectionBoxedRow = Arrays.stream(array[row])
.boxed()
.collect(Collectors.toList());
Collections.reverse(collectionBoxedRow);
array[row] = collectionBoxedRow.stream()
.mapToInt(Integer::intValue)
.toArray();
}
}
首先,像以前的方法一樣,我們首先循環原始的二維數組。
然後我們將int[]中的每一行裝箱到List<Integer>並且儲存。我們這樣做是因為Collections.reverse()只適用於物件集合,而 Java 沒有可以恢復int[]類型的公共 API。
最後,我們使用the mapToInt()和toArray()方法取消裝箱反向裝箱行,並將其指派給索引row處的原始陣列。
相反,如果我們接受List<List<Integer>>作為參數,解決方案就會變得更清晰,因此我們不需要將List轉換為數組,反之亦然:
public static void reverseRowsUsingCollectionsReverse(List<List<Integer>> array) {
array.forEach(Collections::reverse);
}
4. 在流執行期間反轉行
到目前為止,我們已經了解了就地反轉數組的方法。然而,有時我們不想改變輸入,在使用 Java Streams 時就是這種情況。
在本節中,我們將建立一個自訂映射器並收集函數來反轉二維數組的行。
4.1.建立逆序映射器
我們首先看看如何建立一個以相反順序傳回輸入清單的函數:
static <T> List <T> reverse(List<T> input) {
Object[] tempArray = input.toArray();
Stream<T> stream = (Stream<T>) IntStream.range(0, temp.length)
.mapToObj(i -> temp[temp.length - i - 1]);
return stream.collect(Collectors.toList());
}
此方法接受泛型類型T的a List並傳回它的反轉版本。此處使用泛型有助於處理任何類型的流。
演算法首先使用輸入內容建立一個臨時Object數組。然後,我們透過將每個元素重新映射到其對稱來恢復其元素,類似於我們在 3.1 節中所做的。最後,我們將結果收集到一個清單中並返回。
現在,我們可以在二維數組的流中使用reverse() :
List<List<Integer>> array = asList(asList(1, 2, 3), asList(3, 2, 1), asList(2, 1, 3));
List<List<Integer>> result = array.stream()
.map(ReverseArrayElements::reverse)
.collect(Collectors.toList());
我們在使用原始 2d 陣列開啟的流中使用reverse()作為map()方法的 lambda 函數。然後,我們將結果收集反轉為新的二維數組。
4.2.實現逆序收集器
我們可以使用客製化的收集器來實現相同的目的。讓我們看看它是如何運作的:
static <T> Collector<T, ? , List<T>> toReversedList() {
return Collector.of(
ArrayDeque::new,
(Deque <T> deque, T element) -> deque.addFirst(element),
(d1, d2) -> {
d2.addAll(d1);
return d2;
},
ArrayList::new
);
}
上面的方法傳回一個收集器,因此我們可以在Stream's collect()方法中使用它並反轉輸入列表的元素。為此,我們使用Collector.of ()方法傳遞 4 個參數:
- 我們將使用
ArrayDeque的Supplier來幫助我們恢復輸入。選擇ArrayDeque是因為它提供了在第一個索引處的高效插入。 - 累加每個輸入數組元素的函數,將其添加到累加器
ArrayDeque的第一個位置。 - 另一個函數將一個累加器
ArrayDeque,d1的結果與另一個累加器d2結合。然後,我們返回d2. - 組合中間結果後,我們使用整理器函數
ArrayList::new將ArrayDequed2轉換為ArrayList。
簡而言之,我們從左到右讀取輸入數組,並將其元素添加到中間ArrayDeque.這保證了在執行結束時,累積的ArrayDeque將包含反轉的陣列。然後,我們將其轉換為列表並返回。
然後,我們可以在流中使用toReversedList() :
List<List<Integer>> array = asList(asList(1, 2, 3), asList(3, 2, 1), asList(2, 1, 3));
List<List<Integer>> result = array.stream()
.map(a -> a.stream().collect(toReversedList()))
.collect(Collectors.toList());
我們可以將toReversedList()直接傳遞到在原始二維數組行的流中打開的collect() 。然後,我們將反轉的行收集到一個新清單中以產生最終結果。
5. 結論
在本文中,我們探索了幾種用於反轉二維數組行的演算法。此外,我們還建立了用於反轉行的自訂映射器和收集器,並將它們用於 2d 陣列流中。
與往常一樣,原始碼可以在 GitHub 上取得。