Java中将数组中的零移动到末尾的方法 | Baeldung
Java中将数组中的零移动到末尾的方法 | Baeldung
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[]数组使用零作为元素的默认值。因此，当我们初始化_result_数组时，我们不需要显式地用零填充它。
- 当我们在测试中断言两个数组的等同时，我们应该使用assertArrayEquals()而不是assertEquals()。
在这种解决方案中，我们只遍历输入数组一次。因此，这种方法具有线性时间复杂度：O(n)。然而，由于它复制了输入数组，其空间复杂度是O(n)。
接下来，让我们探讨如何改进这个解决方案，以实现原地排列，以保持恒定的空间复杂度O(1)。
4. 具有线性时间复杂度的原地排列
让我们重新审视“初始化新数组”的方法。我们维持了一个**非零指针(idx)**在新数组上，以便我们知道一旦在原始数组中检测到非零值，需要更新_result_数组中的哪个元素。
实际上，我们可以在输入数组上设置非零指针。这样，当我们迭代输入数组时，我们可以将非零元素移动到前面，保持它们的相对顺序。完成迭代后，我们将用零填充剩余的位置。
让我们以输入数组为例来理解这个算法是如何工作的：
迭代指针: v
非零指针: ^
v
42, 2, 0, 3, 4, 0
^（用42替换42）
v
42, 2, 0, 3, 4, 0
^（用2替换2）
v
42, 2, 0, 3, 4, 0
^
v
42, 2, 3, 3, 4, 0
^（用3替换0）
v
42, 2, 3, 4, 4, 0
^（用4替换3）
v
42, 2, 3, 4, 4, 0
^
最后一步：用0填充剩余的位置：
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上找到。
OK