283.移动零

LeetCode LeetCode 数组热题100 双指针

发布时间 : 2000-01-10 02:08

字数:1.5k 阅读 :

评论:

283.移动零

283.移动零

283.1 题目

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

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

示例 1：

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

示例 2：

输入：nums = [0]
输出：[0]

提示：

1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1

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

283.2 题解

方法一：遍历数组非零前移

思路

使用一个指针记录非零元素应放置的位置。遍历数组，遇到非零元素就放到该位置，最后将剩余位置填充零。

具体步骤：

初始化 index = 0，指向下一个非零元素应放置的位置。
遍历数组：
- 如果当前元素不为零：nums[index++] = num
将 index 到数组末尾的位置填充零。

举例：对于 nums = [0,1,0,3,12]：

遍历：0 跳过，1 放到 index=0，0 跳过，3 放到 index=1，12 放到 index=2
此时 index=3，数组为 [1,3,12,3,12]
填充零：nums[3]=0，nums[4]=0
结果：[1,3,12,0,0]

复杂度分析

时间复杂度：O(n)，遍历数组两次。
空间复杂度：O(1)，原地修改。

代码

// 方法一：遍历数组非零往移动
// 遇到非零元素就往前移动
static void MoveZeroes1(int[] nums)
{
    int index = 0; // 用于记录当前非零元素的位置
    // 遍历数组，遇到非零元素就往前移动
    foreach (int num in nums)
    {
        if (num != 0)
        {
            nums[index++] = num; // 将非零元素移到数组的前面，同时更新 index
        }
    }

    // 将剩余位置补充为零
    while (index < nums.Length)
    {
        nums[index++] = 0; // 将剩余位置补充为零
    }
}

方法二：双指针法

思路

使用双指针，一个指针遍历数组，另一个指针记录非零元素的位置。遇到非零元素时，与记录位置的元素交换，实现非零元素前移。

核心思想：交换而非覆盖，一次遍历完成。

具体步骤：

初始化 index = 0，指向下一个非零元素应放置的位置。
遍历数组 i 从 0 到 n-1：
- 如果 nums[i] != 0 且 index != i：交换 nums[index] 和 nums[i]
- index++
非零元素被交换到前面，零被交换到后面。

举例：对于 nums = [0,1,0,3,12]：

i=0：nums[0]=0，跳过
i=1：nums[1]=1 != 0，index=0 != i，交换 nums[0] 和 nums[1]，数组变为 [1,0,0,3,12]，index=1
i=2：nums[2]=0，跳过
i=3：nums[3]=3 != 0，index=1 != i，交换 nums[1] 和 nums[3]，数组变为 [1,3,0,0,12]，index=2
i=4：nums[4]=12 != 0，index=2 != i，交换 nums[2] 和 nums[4]，数组变为 [1,3,12,0,0]，index=3
结果：[1,3,12,0,0]

复杂度分析

时间复杂度：O(n)，遍历一次数组。
空间复杂度：O(1)，原地修改。

代码

// 方法二：双指针法
// 一个指针遍历数组，另一个指针记录非零元素的位置
static void MoveZeroes2(int[] nums)
{
    int index = 0; // 记录非零元素的位置
    // 遍历数组，遇到非零元素就和记录位置的元素交换
    for (int i = 0; i < nums.Length; i++)
    {
        if (nums[i] != 0)
        {
            // 如果 index != i，则说明当前位置有零，需要交换
            if (index != i)
            {
                // 交换非零元素到记录位置的元素的位置
                (nums[index], nums[i]) = (nums[i], nums[index]);
            }

            index++; // 更新记录非零元素位置的指针
        }
    }
}

283.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个数组 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

        // 进阶：你能尽量减少完成的操作次数吗？

        #endregion

        #region 测试

        // 示例 1 测试方法1
        int[] nums1 = { 0, 1, 0, 3, 12 };
        MoveZeroes1(nums1);
        Console.Write("示例1 方法1 输出：");
        PrintArray(nums1);

        // 示例 1 测试方法2
        int[] nums1_2 = { 0, 1, 0, 3, 12 };
        MoveZeroes2(nums1_2);
        Console.Write("示例1 方法2 输出：");
        PrintArray(nums1_2);

        // 示例 2 测试方法1
        int[] nums2 = { 0 };
        MoveZeroes1(nums2);
        Console.Write("示例2 方法1 输出：");
        PrintArray(nums2);

        // 示例 2 测试方法2
        int[] nums2_2 = { 0 };
        MoveZeroes2(nums2_2);
        Console.Write("示例2 方法2 输出：");
        PrintArray(nums2_2);

        #endregion
    }

    #region 答案

    // 方法一：遍历数组非零往移动
    // 遇到非零元素就往前移动
    static void MoveZeroes1(int[] nums)
    {
        int index = 0; // 用于记录当前非零元素的位置
        // 遍历数组，遇到非零元素就往前移动
        foreach (int num in nums)
        {
            if (num != 0)
            {
                nums[index++] = num; // 将非零元素移到数组的前面，同时更新 index
            }
        }

        // 将剩余位置补充为零
        while (index < nums.Length)
        {
            nums[index++] = 0; // 将剩余位置补充为零
        }
    }

    // 方法二：双指针法
    // 一个指针遍历数组，另一个指针记录非零元素的位置
    static void MoveZeroes2(int[] nums)
    {
        int index = 0; // 记录非零元素的位置
        // 遍历数组，遇到非零元素就和记录位置的元素交换
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] != 0)
            {
                // 如果 index != i，则说明当前位置有零，需要交换
                if (index != i)
                {
                    // 交换非零元素到记录位置的元素的位置
                    (nums[index], nums[i]) = (nums[i], nums[index]);
                }

                index++; // 更新记录非零元素位置的指针
            }
        }
    }

    #endregion

    #region 辅助方法

    // 辅助方法：打印数组
    static void PrintArray(int[] nums)
    {
        foreach (var num in nums)
        {
            Console.Write(num + " ");
        }

        Console.WriteLine();
    }

    #endregion
}

283.4 运行结果

示例1 方法1 输出：1 3 12 0 0 
示例1 方法2 输出：1 3 12 0 0 
示例2 方法1 输出：0 
示例2 方法2 输出：0

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com