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[]数组的元素默认值为零**。因此，我们在初始化结果数组时无需显式填充零。 - 当我们在测试中比较两个数组的相等性时，应使用
assertArrayEquals()**而不是assertEquals()**。
在这个解决方案中，我们只遍历输入数组一次。因此，**这种方法的时间复杂度是线性的：O(n)。然而，由于它复制了输入数组，空间复杂度是O(n)**。
现在，我们将探讨如何改进这个解决方案，以实现原地排列，从而保持常数空间复杂度O(1)。
4. 原地排列（线性时间复杂度）
让我们再次回顾一下“初始化新数组”的方法。我们在新数组上维护了一个**非零指针(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)**。
5. 总结
在这篇文章中，我们探讨了将整数数组中的零移动到末尾的两种方法，并讨论了它们在时间和空间复杂度方面的性能。
如往常一样，每个示例的完整源代码可以在GitHub上找到。