Java中将零移至数组末尾

当我们在 Java 中使用数组时，一项常见任务是重新排列数组以优化其结构。一种这样的场景涉及将零移动到数组的末尾。
在本教程中，我们将探索使用 Java 实现此任务的不同方法。

在我们深入实现之前，我们首先了解这个问题的要求。

我们的输入是一个整数数组。我们的目标是重新排列整数，以便将所有零移动到数组的末尾。此外，必须保留那些非零元素的顺序。

举个例子可以帮助我们快速理解问题。假设我们有一个整数数组：
[ 42, 2, 0, 3, 4, 0 ]

重新排列其元素后，我们期望获得一个相当于以下结果的数组：
static final int[] EXPECTED = new int[] { 42, 2, 3, 4, 0, 0 };

接下来，我们将介绍解决该问题的两种方法。我们还将简要讨论它们的性能特征。

1、使用附加数组
为了解决这个问题，首先出现的想法可能是使用一个额外的数组。

假设我们创建一个新数组并将其命名为结果。该数组初始化为与输入数组相同的长度，并且其所有元素都设置为零。

接下来，我们遍历输入数组。每当遇到非零数字时，我们都会相应地更新结果数组中的相应元素。

让我们实现这个想法：

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) 空间复杂度。

2、线性时间复杂度的就地安排
让我们首先回顾一下“初始化新数组”方法。我们在新数组上维护了一个非零指针（idx），以便在原始数组中检测到非零值时知道结果数组中的哪个元素需要更新。

事实上，我们可以在输入数组上设置非零指针。这样，当我们迭代输入数组时，我们可以将非零元素移到前面，保持它们的相对顺序。完成迭代后，我们将用零填充剩余位置。

让我们以输入数组为例来了解该算法的工作原理：

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) 不变。

结论
在本文中，我们探讨了两种将零重新定位到整数数组末尾的方法。此外，我们还讨论了它们在时间和空间复杂性方面的表现。