移动零

题目要求

编写一个函数，该函数接受一个整数数组nums作为参数。函数的目标是将数组中所有的 0 元素移动到数组的末尾，同时保持所有非零元素的原有顺序不变。在移动元素时，不能使用额外的数组来复制，必须在原数组上进行操作，即原地修改数组。

解题思路

解决这个问题的关键是要在遍历数组的同时，找到一种有效的方式来将非零元素向前移动，而将 0 元素留在数组的后部。以下是一个高效的解题步骤：

初始化一个指针（比如叫nonZeroIndex），用于记录下一个非零元素应该放置的位置。
遍历数组nums，对于每个元素执行以下操作：
- 如果当前元素不是 0，将其移动到nonZeroIndex指示的位置，然后将nonZeroIndex加 1。
- 如果当前元素是 0，则不做任何操作，继续遍历。
遍历完成后，nonZeroIndex及其之后的所有位置都应该被填充为 0，因为所有的非零元素都已经移动到了数组的前部。

这个方法的关键点在于，nonZeroIndex指针始终指向当前已处理序列的末尾的下一个位置，这样可以确保非零元素的相对顺序不变，并且所有的 0 都被推到数组的末尾。

这种方法的时间复杂度为 O(n)，因为我们只需要遍历数组一次。空间复杂度为 O(1)，因为我们没有使用额外的存储空间。

Golang 版本

package main

import "fmt"

// moveZeroes 函数将所有0移动到数组末尾，同时保持非零元素的相对顺序。
func moveZeroes(nums []int) {
    nonZeroIndex := 0 // 初始化非零元素应该放置的位置

    // 遍历数组，将非零元素移动到nonZeroIndex的位置
    for _, num := range nums {
        if num != 0 {
            nums[nonZeroIndex] = num
            nonZeroIndex++
        }
    }

    // 将nonZeroIndex之后的所有元素设置为0
    for i := nonZeroIndex; i < len(nums); i++ {
        nums[i] = 0
    }
}

func main() {
    nums := []int{0, 1, 0, 3, 12}
    moveZeroes(nums)
    fmt.Println(nums) // 输出应为[1, 3, 12, 0, 0]
}

C++版本

#include <iostream>
#include <vector>

// moveZeroes函数将所有0移动到数组末尾，同时保持非零元素的相对顺序。
void moveZeroes(std::vector<int>& nums) {
    int nonZeroIndex = 0; // 初始化非零元素应该放置的位置

    // 遍历数组，将非零元素移动到nonZeroIndex的位置
    for (int num : nums) {
        if (num != 0) {
            nums[nonZeroIndex++] = num;
        }
    }

    // 将nonZeroIndex之后的所有元素设置为0
    for (int i = nonZeroIndex; i < nums.size(); ++i) {
        nums[i] = 0;
    }
}

int main() {
    std::vector<int> nums = {0, 1, 0, 3, 12};
    moveZeroes(nums);

    // 输出结果，应为[1, 3, 12, 0, 0]
    for (int num : nums) {
        std::cout << num << ' ';
    }
    std::cout << std::endl;

    return 0;
}

Python 版本

def move_zeroes(nums):
    non_zero_index = 0  # 初始化非零元素应该放置的位置

    # 遍历数组，将非零元素移动到non_zero_index的位置
    for num in nums:
        if num != 0:
            nums[non_zero_index] = num
            non_zero_index += 1

    # 将non_zero_index之后的所有元素设置为0
    for i in range(non_zero_index, len(nums)):
        nums[i] = 0

# 测试代码
if __name__ == "__main__":
    nums = [0, 1, 0, 3, 12]
    move_zeroes(nums)
    print(nums)  # 输出应为[1, 3, 12, 0, 0]

Java 版本

public class MoveZeroes {
    public static void moveZeroes(int[] nums) {
        int nonZeroIndex = 0; // 初始化非零元素应该放置的位置

        // 遍历数组，将非零元素移动到nonZeroIndex的位置
        for (int num : nums) {
            if (num != 0) {
                nums[nonZeroIndex++] = num;
            }
        }

        // 将nonZeroIndex之后的所有元素设置为0
        for (int i = nonZeroIndex; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 3, 12};
        moveZeroes(nums);

        // 输出结果，应为[1, 3, 12, 0, 0]
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
}

Rust 版本

fn move_zeroes(nums: &mut Vec<i32>) {
    let mut non_zero_index = 0; // 初始化非零元素应该放置的位置

    // 遍历数组，将非零元素移动到non_zero_index的位置
    for &num in nums.iter() {
        if num != 0 {
            nums[non_zero_index] = num;
            non_zero_index += 1;
        }
    }

    // 将non_zero_index之后的所有元素设置为0
    for i in non_zero_index..nums.len() {
        nums[i] = 0;
    }
}

fn main() {
    let mut nums = vec![0, 1, 0, 3, 12];
    move_zeroes(&mut nums);

    // 输出结果，应为[1, 3, 12, 0, 0]
    for num in nums {
        print!("{} ", num);
    }
}

总结

无论是在 Go, C++, Python, Java 还是 Rust 语言中，解决将数组中所有 0 移动到末尾的问题的基本思路都是相同的。以下是这个问题的通用解决方案的步骤：

初始化一个变量（例如nonZeroIndex），用于跟踪数组中非零元素应该插入的位置。
遍历数组，对于每个非零元素，将其移动到nonZeroIndex指示的位置，并将nonZeroIndex递增。
在数组剩余的位置上填充 0，这些位置从nonZeroIndex开始到数组的末尾。

这个算法的时间复杂度是 O(n)，因为它只需要遍历数组一次。空间复杂度是 O(1)，因为它不需要额外的存储空间，所有的操作都是在原地完成的。

在不同的编程语言中，这个算法的实现细节可能略有不同，例如在 Rust 中使用iter()方法来遍历数组，在 Python 中直接遍历数组，在 C++和 Java 中使用范围基的 for 循环。但是，核心算法和逻辑是一致的。

hot-100