Java 中将零移到末尾

给定一个未排序整数数组。我们的任务是将所有零元素移到末尾，将非零元素移到前面。注意，非零元素的相对排列不应被打乱。以下示例将使事情更清晰。

示例 1

输入： int arr[] = {6, 7, 0, 2, 1, 78, 0, 56, 0, 4}

输出： arr[] = {6, 7, 2, 1, 78, 56, 4, 0, 0, 0}

解释： 在保持非零元素相对顺序的情况下，这是唯一可能的解决方案。注意，相对顺序意味着如果一个元素的位置在另一个元素之前，那么该顺序必须在输出中保持。在输入数组中，78 在 56 之前；因此，在输出中，78 也在 56 之前。同样的逻辑可以应用于数组的其他非零元素。

示例 2

输入： int arr[] = {8, 9, 2, 3, 0, 0, 0}

输出： arr[] = {8, 9, 2, 3, 0, 0, 0}

解释： 在输入数组中，零已经位于末尾。因此，无需任何修改，我们可以直接返回输入数组。

方法：使用辅助数组

这个方法很简单。请观察以下步骤。

步骤 1： 创建一个与输入数组大小相同的辅助数组。

步骤 2： 创建一个变量 zeroCount，并将其初始化为零。同时，创建一个变量 outputIndex，并将其初始化为 0。

步骤 3： 使用循环遍历输入数组的元素。如果遇到值为零的元素，则将 zeroCount 增加 1。如果遇到非零元素，则将该元素的值复制到 auxiliarArray[outputIndex] 中，并将 outputIndex 的值增加 1。

步骤 4： 在辅助数组的末尾添加 0。零的数量应等于变量 zeroCount 中包含的值。这可以通过循环完成。

步骤 5： 在控制台上显示输出数组。

实施

请观察上述步骤的实现。

文件名： MoveZeros.java

输出

For the following array: 
6 7 0 2 1 78 0 56 0 4 
The answer after moving the zero at the end is: 
6 7 2 1 78 56 4 0 0 0 

For the following array: 
8 9 2 3 0 0 0 
The answer after moving the zero at the end is: 
8 9 2 3 0 0 0

复杂度分析： 由于在 solve() 方法中使用了循环遍历元素并在末尾添加零，因此程序的时间复杂度为 O(N)。此外，还使用了一个辅助数组来存储结果。因此，程序的空间复杂度为 O(N)，其中 N 是输入数组中存在的元素总数。

我们将在以下方法中优化空间复杂度。

方法：使用双指针

我们将使用两个指针。一个指向零值元素，另一个指向非零值元素。任务是将零值元素移到末尾。因此，非零指针仅在零元素指针之后遇到非零元素时才指向。每当我们看到非零和零指针都已设置时，就可以交换输入数组中这些位置的元素。之后，我们将零指针进一步移动。我们还会移动非零指针，直到找到非零元素。当非零指针到达输入数组的末尾时，我们停止。下图对此进行了说明。

实施

文件名： MoveZeros1.java

输出

For the following array: 
6 7 0 2 1 78 0 56 0 4 
The answer after moving the zero at the end is: 
6 7 2 1 78 56 4 0 0 0 

For the following array: 
8 9 2 3 0 0 0 
The answer after moving the zero at the end is: 
8 9 2 3 0 0 0

复杂度分析

程序的时间复杂度与之前的程序相同。由于程序中没有使用辅助空间，因此程序的空间复杂度是常数，即 O(1)。