LeetCode 283题：移动零

LeetCode 283题：移动零 (Move Zeroes)

LeetCode 第283题要求将数组中的所有零移动到数组的末尾，同时保持非零元素的相对顺序。

题目描述

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

注意:

1. 必须在原数组上操作，不能拷贝额外的数组。
2. 尽量减少操作次数。

示例

示例 1：

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

示例 2：

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

解题思路

1. 双指针法：

   • 定义两个指针：i 和 j。
   • i 指向非零元素要存储的位置，j 遍历整个数组寻找非零元素。
   • 如果找到非零元素，则将其移动到 i 的位置，并将 i 向后移动。
   • 最后，从 i 开始的剩余位置填充为零。

2. 遍历两次：

   • 第一次遍历数组，将所有非零元素移到前面。
   • 第二次从非零结束的位置开始，将剩余的位置填充为零。

3. 复杂度分析：

   • 时间复杂度：$O(n)$，其中 $n$ 是数组的长度，只需遍历数组两次。
   • 空间复杂度：$O(1)$，没有使用额外的数组存储。

C语言代码实现

以下是基于双指针的代码实现：

#include <stdio.h>

/**
 * 移动零
 * @param nums: 输入数组
 * @param numsSize: 数组的大小
 */
void moveZeroes(int* nums, int numsSize) {
    int i = 0; // i 指向非零元素要存储的位置
    for (int j = 0; j < numsSize; j++) {
        if (nums[j] != 0) {  // 如果找到非零元素
            nums[i] = nums[j]; // 将非零元素移动到索引 i 的位置
            i++;               // 更新 i 的位置
        }
    }
    for (; i < numsSize; i++) {
        nums[i] = 0; // 将剩余的位置填充为 0
    }
}

int main() {
    int nums1[] = {0, 1, 0, 3, 12};
    int nums2[] = {0, 0, 1};

    moveZeroes(nums1, 5);
    moveZeroes(nums2, 3);

    printf("Test Case 1: ");
    for (int i = 0; i < 5; i++) {
        printf("%d ", nums1[i]);
    }
    printf("\n");

    printf("Test Case 2: ");
    for (int i = 0; i < 3; i++) {
        printf("%d ", nums2[i]);
    }
    printf("\n");

    return 0;
}

逐行解释代码

函数 moveZeroes

void moveZeroes(int* nums, int numsSize) {
    int i = 0; // i 指向非零元素要存储的位置

• 定义一个指针 i，用于记录非零元素存储的目标位置，初始值为 0。

    for (int j = 0; j < numsSize; j++) {
        if (nums[j] != 0) {  // 如果找到非零元素
            nums[i] = nums[j]; // 将非零元素移动到索引 i 的位置
            i++;               // 更新 i 的位置
        }
    }

• 使用指针 j 遍历数组：
  • 如果 nums[j] != 0，说明当前元素是非零，将其移动到 nums[i]。
  • 然后将 i 向后移动，以便存储下一个非零元素。

    for (; i < numsSize; i++) {
        nums[i] = 0; // 将剩余的位置填充为 0
    }

• 遍历结束后，指针 i 指向非零元素的最后一个位置。
• 从 i 开始，将数组剩余的所有位置填充为 0。

测试代码 main

int main() {
    int nums1[] = {0, 1, 0, 3, 12};
    int nums2[] = {0, 0, 1};

    moveZeroes(nums1, 5);
    moveZeroes(nums2, 3);

    printf("Test Case 1: ");
    for (int i = 0; i < 5; i++) {
        printf("%d ", nums1[i]);
    }
    printf("\n");

    printf("Test Case 2: ");
    for (int i = 0; i < 3; i++) {
        printf("%d ", nums2[i]);
    }
    printf("\n");

    return 0;
}

• 定义了两个测试用例：
  • nums1 = {0, 1, 0, 3, 12}
  • nums2 = {0, 0, 1}
• 调用 moveZeroes 函数进行操作。
• 打印出修改后的数组，验证结果。

测试结果

运行代码后输出：

Test Case 1: 1 3 12 0 0 
Test Case 2: 1 0 0 

复杂度分析

1. 时间复杂度：

   • 遍历数组两次，每次 $O(n)$，总复杂度为 $O(n)$。

2. 空间复杂度：

   • 没有使用额外存储，空间复杂度为 $O(1)$。