在 Java 中將零移至數組末尾

1. 概述

當我們在 Java 中使用陣列時，一項常見任務是重新排列數組以優化其結構。一種這樣的場景涉及將零移動到數組的末尾。

在本教程中，我們將探索使用 Java 實作此任務的不同方法。

2.問題介紹

在我們深入實現之前，我們首先了解這個問題的要求。

我們的輸入是一個整數陣列。我們的目標是重新排列整數，以便將所有零移動到陣列的末端。此外，必須保留那些非零元素的順序。

舉個例子可以幫助我們快速理解問題。假設我們有一個整數數組：

[ 42, 2, 0, 3, 4, 0 ]

重新排列其元素後，我們期望獲得一個相當於以下結果的陣列：

static final int[] EXPECTED = new int[] { 42, 2, 3, 4, 0, 0 };

接下來，我們將介紹解決該問題的兩種方法。我們還將簡要討論它們的性能特徵。

3. 使用附加數組

為了解決這個問題，首先出現的想法可能是使用額外的陣列。

假設我們建立一個新數組並將其命名為result.此數組初始化為與輸入數組相同的長度，並且其所有元素都設為零。

接下來，我們遍歷輸入陣列。每當遇到非零數字時，我們都會相應地更新result數組中的相應元素。

讓我們實現這個想法：

int[] array = new int[] { 42, 2, 0, 3, 4, 0 };
 int[] result = new int[array.length];
 int idx = 0;
 for (int n : array) {
 if (n != 0) {
 result[idx++] = n;
 }
 }
 assertArrayEquals(EXPECTED, result);

正如我們所看到的，程式碼非常簡單。有兩件事值得一提：

• 在 Java 中， int[]陣列使用零作為 elements 的預設值。因此，在初始化結果數組時，我們不需要明確地用零填充它。
• 當我們在測試中斷言兩個陣列相等時，我們應該使用assertArrayEquals()而不是**assertEquals()** .

在此解決方案中，我們僅遍歷輸入數組一次。因此，這種方法具有線性時間複雜度： O(n) 。但是，由於它複製輸入數組，因此其空間複雜度為 O(n) 。

接下來，我們探討如何改進這個解決方案，實現就地排列，以保持恆定的 O(1) 空間複雜度。

4. 線性時間複雜度的就地安排

讓我們先回顧一下「初始化新數組」方法。我們在新數組上維護了一個非零指標（ idx ） ，以便在原始數組中檢測到非零值時知道result數組中的哪個元素需要更新。

事實上，我們可以在輸入數組上設定非零指標。這樣，當我們迭代輸入數組時，我們可以將非零元素移到前面，並保持它們的相對順序。完成迭代後，我們將用零填滿剩餘位置。

讓我們以輸入數組為例來了解演算法的工作原理：

Iteration pointer: v
 Non-zero-pointer: ^

 v
 42, 2, 0, 3, 4, 0
 ^ (replace 42 with 42)

 v
 42, 2, 0, 3, 4, 0
 ^ (replace 2 with 2)

 v
 42, 2, 0, 3, 4, 0
 ^

 v
 42, 2, 3, 3, 4, 0
 ^ (replace 0 with 3)

 v
 42, 2, 3, 4, 4, 0
 ^ (replace 3 with 4)

 v
 42, 2, 3, 4, 4, 0
 ^

 The final step: Fill 0s to the remaining positions:
 v
 42, 2, 3, 4, 0, 0
 ^

接下來我們來實作一下這個邏輯：

int[] array = new int[] { 42, 2, 0, 3, 4, 0 };
 int idx = 0;
 for (int n : array) {
 if (n != 0) {
 array[idx++] = n;
 }
 }
 while (idx < array.length) {
 array[idx++] = 0;
 }
 assertArrayEquals(EXPECTED, array);

我們可以看到，上面的程式碼中沒有引入額外的陣列。非零指標idx追蹤非零元素應放置的位置。在迭代過程中，如果當前元素非零，我們將其移到前面並遞增指標。完成迭代後，我們使用while循環將剩餘位置填充為零。

此方法執行就地重新排列。也就是說，不需要額外的空間。因此，其空間複雜度為 O(1) 。

在最壞的情況下，輸入數組中的所有元素都為零，其缺點是idx指針在迭代後保持靜止。因此，後續的while循環將再次遍歷整個數組。儘管如此，由於迭代執行了恆定次數，因此總體時間複雜度保持在 O(n) 不變。

5. 結論

在本文中，我們探討了兩種將零重新定位到整數陣列末端的方法。此外，我們也討論了它們在時間和空間複雜性方面的表現。

與往常一樣，範例的完整原始程式碼可在 GitHub 上取得。