移动零

题目分析

本题的目标是将数组中的所有 0 移动到数组末尾，并保持其他非零元素的相对顺序，同时要求 原地修改 数组，即不能复制额外的数组。这意味着我们需要用 双指针 和 原地交换 技巧来高效地解决问题。

解题思路

我们可以使用 双指针法 来解决这个问题，其中一个指针 j 用来遍历整个数组，另一个指针 i 记录下一个应该放置非零元素的位置。具体做法如下：

1. 初始化 i = 0，用于记录非零元素应该存放的位置。
2. 遍历数组：
   • 遇到非零元素时，将其 移动到索引 i 位置，然后 i 向前移动。
   • 遇到 0 时，不做任何操作，继续遍历。
3. 遍历结束后，所有 0 会自动被放置到数组末尾。

复杂度分析

• 时间复杂度：O(n)，每个元素最多遍历一次，因此时间复杂度为线性。
• 空间复杂度：O(1)，仅使用了常数额外空间，符合题目要求的 原地修改。

代码实现

Python 解法

class Solution:
    def moveZeroes(self, nums):
        n = len(nums)
        i = 0  # 记录非零元素应放置的位置
        
        # 遍历数组，将非零元素移到前面
        for j in range(n):
            if nums[j] != 0:
                nums[i], nums[j] = nums[j], nums[i]  # 交换非零元素到前面
                i += 1  # 移动非零元素位置索引

# 读入数据并调用函数
n = int(input().strip())
nums = list(map(int, input().split()))
Solution().moveZeroes(nums)
print(" ".join(map(str, nums)))

Java 解法

import java.util.*;

public class Main {  
    public class Solution { 
        public void moveZeroes(int[] nums) {
            int i = 0; // 记录非零元素应存放的位置
            
            // 遍历数组，将非零元素放到前面
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] != 0) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    i++; // 更新非零存放位置
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 读取数组长度
        int[] nums = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

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

        for (int i = 0; i < n; i++) {
            System.out.print(nums[i] + (i < n - 1 ? " " : ""));
        }
    }
}

C++ 解法

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i = 0; // 记录非零元素应存放的位置
        
        // 遍历数组，将非零元素放到前面
        for (int j = 0; j < nums.size(); j++) {
            if (nums[j] != 0) {
                swap(nums[i], nums[j]); // 交换非零元素到前面
                i++; // 更新非零存放位置
            }
        }
    }
};

int main() {
    int n;
    cin >> n; // 读取数组长度
    vector<int> nums(n);
    
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    Solution solution;
    solution.moveZeroes(nums);

    for (int i = 0; i < n; i++) {
        cout << nums[i] << (i < n - 1 ? " " : "");
    }
    return 0;
}

Leetcode 4.移动零-原题链接

题目内容

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

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

输入描述

输入共两行。

• 第一行为两个个整数$n$，代表数组$nums$的长度。

• 第二行为$n$个整数$nums_0,nums_1,...,nums_{n-1}$，数字之间以空格分隔。

输出描述

输出操作后的数组，以空格分隔。

样例1

输入

5
0 1 0 3 12

输出

1 3 12 0 0

样例2

输入

1
0

输出

0

提示

• $1 <= nums.length <= 10^4$
• $-2^{31 }<= nums[i] <= 2^{31}-1$

进阶

你能尽量减少完成的操作次数吗？