283. 移动零

题目：移动零

描述：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

要求：

• 必须在不复制数组的情况下原地对数组进行操作。

---

示例：

示例 1:

输入: nums = [0, 1, 0, 3, 12]
输出: [1, 3, 12, 0, 0]

示例 2:

输入: nums = [0]
输出: [0]

---

解题思路：

为了在原地操作并保持相对顺序，我们可以使用 双指针法。通过一个指针遍历数组，另一个指针记录当前非零元素应放置的位置。

算法步骤：

1. 初始化一个指针 nonZeroIndex，它表示当前非零元素应放置的位置。
2. 遍历数组，当遇到非零元素时，将其移动到 nonZeroIndex 指针的位置，并将 nonZeroIndex 向后移动一位。
3. 遍历完成后，nonZeroIndex 后面的所有位置都应当是零，可以将它们置为 0。

通过这种方式，非零元素会被移动到数组的前面，而所有零会被自动推到数组的末尾。

代码实现：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        Solution solution = new Solution();
        solution.moveZeroes(nums);

        // 输出结果
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]);
            if (i < nums.length - 1) {
                System.out.print(" ");
            }
        }
        System.out.println();

        scanner.close();
    }
}

class Solution {
    public void moveZeroes(int[] nums) {
        int nonZeroIndex = 0;  // 用于记录非零元素应该放置的位置

        // 遍历数组，将非零元素移动到前面
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                // 交换当前非零元素与非零位置的元素
                int temp = nums[i];
                nums[i] = nums[nonZeroIndex];
                nums[nonZeroIndex] = temp;
                nonZeroIndex++;
            }
        }
    }
}

---

时间复杂度分析：

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需遍历数组一次。
• 空间复杂度：O(1)，我们仅使用了常数级别的额外空间，符合原地操作的要求。

总结：

使用双指针法可以在 O(n) 时间复杂度内完成零元素的移动，同时保持非零元素的顺序不变。通过交换元素的位置，可以高效地解决该问题，而不需要额外的空间来存储数组的副本。