法算day4

移动零

问题描述

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

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

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

示例 2:
输入: nums = [0]
输出: [0]

提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

java版

方法一：双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public void moveZeroes(int[] nums) {
        // 边界情况检查：如果数组为空或长度为0，直接返回
        if (nums == null || nums.length == 0) {
            return;
        }
        
        // 使用双指针法
        // left指针：指向当前应该放置非零元素的位置
        int left = 0;
        
        // 遍历数组
        for (int right = 0; right < nums.length; right++) {
            // 如果当前元素不为0
            if (nums[right] != 0) {
                // 将非零元素移动到left指针的位置
                nums[left] = nums[right];
                // 如果left和right不是同一个位置，说明移动了元素    
                // 需要将原位置设置为0（避免重复）                        
                if (left != right) {
                    nums[right] = 0;
                }
                // left指针向右移动，准备放置下一个非零元素
                left++;
            }
            // 如果当前元素为0，left指针不动，right指针继续向右移动
        }
    }
}

✅ 说明：

  1. left 指针：记录下一个非零元素应该放置的位置
    right 指针：遍历整个数组，寻找非零元素
  2. 时间复杂度：O(n)，只需要遍历数组一次（或两次）
  3. 空间复杂度：O(1)，只使用了常数级别的额外空间

额外补充-增强for循环有一个严重缺陷！

1
2
3
4
5
6
7
8
9
int[] nums = {0, 1, 0, 3, 12};

// 使用增强for循环（有问题！）
for (int num : nums) {
    if (num != 0) {
        nums[insertPos] = num;  // 这里会修改数组！
        insertPos++;
    }
}

执行过程

1
2
3
4
5
6
初始: [0, 1, 0, 3, 12]
第1次循环: num=0 → 跳过
第2次循环: num=1 → nums[0]=1 → 数组变成 [1, 1, 0, 3, 12]
第3次循环: num=0 → 跳过
第4次循环: num=3 → nums[1]=3 → 数组变成 [1, 3, 0, 3, 12]
第5次循环: num=12 → nums[2]=12 → 数组变成 [1, 3, 12, 3, 12]

增强for循环适合只读操作，比如：

1
2
3
4
5
6
7
8
9
10
// 只读操作 - 适合用增强for循环
int sum = 0;
for (int num : nums) {
    sum += num;  // 不修改数组，只是读取值
}

// 或者打印数组
for (int num : nums) {
    System.out.print(num + " ");
}

✅ 总结：
增强for循环：语法简洁，适合只读遍历
传统for循环：功能更强大，可以通过索引修改数组，控制遍历过程

python版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def moveZeroes(nums):
    """
    将数组中的所有0移动到末尾，保持非零元素的相对顺序
    
    参数:
    nums: List[int] - 输入的整数列表
    
    思路:
    使用双指针，left指针记录非零元素应该放置的位置
    right指针遍历整个数组
    """
    left = 0  # left指针：指向下一个非零元素应该放置的位置
    
    # right指针遍历整个数组
    for right in range(len(nums)):
        # 如果当前元素不为0
        if nums[right] != 0:
            # 将非零元素交换到left位置
            nums[left], nums[right] = nums[right], nums[left]
            # left指针向右移动，准备放置下一个非零元素
            left += 1
        # 如果当前元素为0，left指针不动，right指针继续移动

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 测试函数
def test_moveZeroes():
    # 测试用例1
    nums1 = [0, 1, 0, 3, 12]
    moveZeroes(nums1)
    print(f"测试1: {nums1}")  # 应该输出 [1, 3, 12, 0, 0]
    
    # 测试用例2
    nums2 = [0]
    moveZeroes(nums2)
    print(f"测试2: {nums2}")  # 应该输出 [0]
    
    # 测试用例3
    nums3 = [1, 2, 3, 4, 5]
    moveZeroes(nums3)
    print(f"测试3: {nums3}")  # 应该输出 [1, 2, 3, 4, 5]
    
    # 测试用例4
    nums4 = [0, 0, 0, 1, 2]
    moveZeroes(nums4)
    print(f"测试4: {nums4}")  # 应该输出 [1, 2, 0, 0, 0]

# 运行测试
if __name__ == "__main__":
    test_moveZeroes()