1. Overview

1.概述

When we work with arrays in Java, one common task is rearranging arrays to optimize their structure. One such scenario involves moving zeros to the end of an array.

当我们在 Java 中使用数组时，一个常见的任务就是重新排列数组以优化其结构。其中一种情况是将 0 移到数组的末尾。

In this tutorial, we’ll explore different approaches to achieve this task using Java.

在本教程中，我们将探讨使用 Java 实现这一任务的不同方法。

2. Introduction to the Problem

2.问题介绍

Before we dive into the implementation, let’s first understand the requirements of this problem.

在深入实施之前，让我们先了解一下这个问题的要求。

Our input is an array of integers. We aim to rearrange the integers so that all zeros are moved to the end of the array. Further, the order of those non-zero elements must be retained.

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

An example can help us understand the problem quickly. Let’s say we’re given an integer array:

举个例子可以帮助我们快速理解这个问题。假设我们得到一个整数数组：

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

After we rearrange its elements, we expect to obtain an array equivalent to the following as the result:

重新排列元素后，我们希望得到一个与下面等价的数组：

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

Next, we’ll cover two approaches to solving the problem. We’ll also briefly discuss their performance characteristics.

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

3. Using an Additional Array

3.使用附加阵列

To tackle the problem, the first idea that comes up might be to use an additional array.

要解决这个问题，首先想到的可能是使用一个额外的数组。

Let’s say we create a new array and call it result. This array is initialized with the same length as the input array, and all its elements are set to zero.

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

Next, we traverse the input array. Whenever a non-zero number is encountered, we update the corresponding element in the result array accordingly.

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

Let’s implement this idea:

让我们来实现这个想法吧：

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);

As we can see, the code is pretty straightforward. Two things are worth mentioning:

我们可以看到，代码非常简单。有两点值得一提：

In Java, int[] arrays use zero as the default value for elements. So, we don’t need to explicitly fill the result array with zeros when we initialize it.
When we assert the equality of two arrays in a test, we should use assertArrayEquals() instead of assertEquals().

In this solution, we walk through the input array only once. Therefore, this approach has linear time complexity: O(n). However, as it duplicates the input array, its space complexity is O(n).

在此解决方案中，我们只需走一遍输入数组。因此，这种方法具有线性时间复杂性：O(n).但是，由于它会重复输入数组，其空间复杂度为 O(n) 。

Next, let’s explore how to improve this solution to achieve an in-place arrangement to maintain a constant space complexity of O(1).

接下来，让我们探讨如何改进这一解决方案，实现就地排列，以保持 O(1) 的恒定空间复杂度。

4. In-Place Arrangement with Linear Time Complexity

4.具有线性时间复杂性的就地排列

Let’s first revisit the “initializing a new array” approach. We maintained a non-zero-pointer (idx) on the new array so that we know which element in the result array needs to be updated once a non-zero value is detected in the original array.

让我们先重温一下 “初始化新数组 “的方法。我们在新数组上维护了一个 非零指针 (idx)，这样，一旦在原始数组中检测到一个非零值，我们就知道需要更新 result 数组中的哪个元素。

In fact, we can set the non-zero pointer on the input array. In this way, when we iterate through the input array, we can shift non-zero elements to the front, maintaining their relative order. After completing the iteration, we’ll fill the remaining positions with zeros.

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

Let’s take our input array as an example to understand how this algorithm works:

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

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
                ^

Next, let’s implement this logic:

接下来，让我们来实现这一逻辑：

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);

As we can see, no additional array is introduced in the above code. The non-zero-pointer idx keeps track of the position where non-zero elements should be placed. During the iteration, if the current element is non-zero, we move it to the front and increment the pointer. After completing the iteration, we fill the remaining positions with zeros using a while loop.

我们可以看到，上述代码中没有引入额外的数组。非零指针 idx 用于跟踪非零元素应放置的位置。在迭代过程中，如果当前元素为非零，我们会将它移到前面并递增指针。完成迭代后，我们使用 while 循环将剩余的位置填充为零。

This approach performs an in-place rearrangement. That is to say, no extra space is required. Therefore, its space complexity is O(1).

这种方法是就地重新排列。也就是说，不需要额外的空间。因此，其空间复杂度为 O(1)。

In the worst-case scenario where all elements in the input array are zeros, the downside is that the idx pointer remains stationary after the iteration. Consequently, the subsequent while loop will traverse the entire array once more. Despite this, since the iteration is executed a constant number of times, the overall time complexity remains unaffected at O(n).

在输入数组中所有元素均为零的最坏情况下，其缺点是迭代后 idx 指针将保持静止。因此，随后的 while 循环将再次遍历整个数组。尽管如此，由于迭代的执行次数是恒定的，因此总体时间复杂度不受影响，仍为 O(n)。

5. Conclusion

5.结论

In this article, we explored two methods for relocating zeros to the end of an integer array. Additionally, we discussed their performance in terms of time and space complexities.

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

As always, the complete source code for the examples is available over on GitHub.

与往常一样，这些示例的完整源代码可在 GitHub 上获取。