图解数组操作：美团面试题之移动零（双方法解析）

在编程面试中，数组操作是常见的考察点之一。本文将探讨如何解决一道来自美团的面试题——移动零。题目要求将数组中的所有零元素移动到数组的末尾，同时保持非零元素原有的相对顺序不变。我们将通过两次遍历和一次遍历两种方法来解决这个问题。

题目描述

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

例如，给定数组 [0,1,0,3,12]，处理后的结果应为 [1,3,12,0,0]。

需要注意的是，此操作必须直接在给定的数组上进行，不允许使用额外的数组空间，并且尽量减少操作次数。

题目链接：LeetCode - Move Zeroes

方法一：两次遍历

该方法使用两个指针 i 和 j。第一次遍历时，j 记录非零元素的数量。每当遇到非零元素时，就将其移到数组的前面部分。完成第一次遍历后，j 的值即为最后一个非零元素的位置。接着，从 j 开始的剩余位置全部设为零。

这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)。

Java 实现：

public class Solution {    public void moveZeroes(int[] nums) {        if (nums == null) return;        int j = 0; // 记录非零元素的位置        for (int i = 0; i 

Python 实现：

class Solution:    def moveZeroes(self, nums):        if not nums: return        j = 0 # 记录非零元素的位置        for i in range(len(nums)):            if nums[i]:                nums[j] = nums[i]                j += 1        # 剩余位置填充零        for i in range(j, len(nums)):            nums[i] = 0

方法二：一次遍历

此方法借鉴了快速排序的思想。选择 0 作为分界点，将所有非零元素置于 0 的左侧，0 则置于右侧。利用两个指针 i 和 j，当 nums[i] 不等于 0 时，与 nums[j] 交换位置，然后递增 j。

这种方式同样具有 O(n) 的时间复杂度和 O(1) 的空间复杂度。

Java 实现：

public class Solution {    public void moveZeroes(int[] nums) {        if (nums == null) return;        int j = 0; // 记录非零元素的位置        for (int i = 0; i 

Python 实现：

class Solution:    def moveZeroes(self, nums):        if not nums: return        j = 0 # 记录非零元素的位置        for i in range(len(nums)):            if nums[i]:                nums[j], nums[i] = nums[i], nums[j]                j += 1

以上两种方法都能有效地解决问题，具体选择哪种取决于实际应用场景和个人偏好。希望本文对你有所帮助！