283.移动零

LeetCode LeetCode 数组双指针

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

字数:1.2k 阅读 :

评论:

283.移动零

283.移动零

283.1 题目

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1
输出：1

提示：

1 <= bad <= n <= 2^31 - 1

283.2 题解

遍历数组非零往移动

// 方法一：遍历数组非零往移动
// 遇到非零元素就往前移动
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++; // 更新记录非零元素位置的指针
        }
    }
}

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