27.移除元素

LeetCode LeetCode 数组 双指针
发布时间 :
字数:2.2k 阅读 : 评论:
  1. 27.移除元素
    1. 27.1 题目
    2. 27.2 题解
      1. 头部双指针法
      2. 首尾双指针法
    3. 27.3 代码
    4. 27.4 运行结果

27.移除元素

27.1 题目

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会通过。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数应该返回 k = 2，并且 nums 中的前两个元素均为 2。你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0, 1, 4, 0, 3。注意这五个元素可以任意顺序返回。你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

  • 0 <= nums.length <= 100
  • -50 <= nums[i] <= 50
  • val 是任意整数

27.2 题解

头部双指针法

// 方法一：头部双指针法
// 遍历整个数组，并在每次fast遇到不等于目标值的元素时，将其放置在 slow 指针的位置，最终得到移除目标值后的数组和新数组的长度。
static int RemoveElement1(int[] nums, int val)
{
    // 初始化两个指针，一个用于慢速遍历（slow），一个用于快速遍历（fast）
    int slow = 0;
    int fast = 0;

    // 当快速指针没有遍历完整个数组时执行循环
    while (fast < nums.Length)
    {
        // 如果快速指针指向的元素不等于目标值
        if (nums[fast] != val)
        {
            // 将慢速指针指向的位置更新为快速指针指向的元素
            // 假如slow和fast一致其实就自己赋值自己 没有关系
            // 不一致说明遇到目标值了 slow移动慢了 让fast发现不是目标值就填入
            nums[slow] = nums[fast];
            // 移动慢速指针到下一个位置
            ++slow;
        }

        // 移动快速指针到下一个位置
        ++fast;
    }

    // 返回新数组的长度，即不包含目标值的部分
    return slow;
}

首尾双指针法

// 方法二：首尾双指针法
static int RemoveElement2(int[] nums, int val)
{
    // 初始化两个指针，一个用于慢速遍历（slow），一个用于快速遍历（fast）
    int slow = 0;
    int fast = nums.Length - 1;

    // 当慢速指针小于等于快速指针时执行循环
    while (slow <= fast)
    {
        // 如果慢速指针指向的元素等于目标值
        if (nums[slow] == val)
        {
            // 如果快速指针指向的元素不等于目标值
            if (nums[fast] != val)
            {
                // 将慢速指针指向的位置更新为快速指针指向的元素
                nums[slow] = nums[fast];
                // 移动慢速指针到下一个位置
                ++slow;
                // 移动快速指针到前一个位置
                --fast;
            }
            else
            {
                // 如果快速指针指向的元素也等于目标值，只移动快速指针到前一个位置
                --fast;
            }
        }
        else
        {
            // 如果慢速指针指向的元素不等于目标值，直接移动慢速指针到下一个位置
            ++slow;
        }
    }

    // 返回新数组的长度，即不包含目标值的部分
    return slow;
}

27.3 代码

using System;

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

        // 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
        // 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
        // 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

        // 说明:
        // 为什么返回数值是整数，但输出的答案是数组呢?
        // 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

        // 你可以想象内部操作如下:
        // nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
        // int len = removeElement(nums, val);
        // 在函数里修改输入数组对于调用者是可见的。
        // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
        // for (int i = 0; i < len; i++) {
        //     print(nums[i]);
        // }

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 3, 2, 2, 3 };
        int val1 = 3;
        int result1_1 = RemoveElement1(nums1, val1);
        Console.WriteLine($"示例1 方法1 输出长度：{result1_1}");
        Console.Write("示例1 方法1 输出数组：");
        PrintArray(nums1, result1_1);
        int result1_2 = RemoveElement2(nums1, val1);
        Console.WriteLine($"示例1 方法2 输出长度：{result1_2}");
        Console.Write("示例1 方法2 输出数组：");
        PrintArray(nums1, result1_2);


        // 示例 2
        int[] nums2 = { 0, 1, 2, 2, 3, 0, 4, 2 };
        int val2 = 2;
        int result2_1 = RemoveElement1(nums2, val2);
        Console.WriteLine($"示例2 方法1 输出长度：{result2_1}");
        Console.Write("示例2 方法1 输出数组：");
        PrintArray(nums2, result2_1);
        int result2_2 = RemoveElement2(nums2, val2);
        Console.WriteLine($"示例2 方法2 输出长度：{result2_2}");
        Console.Write("示例2 方法2 输出数组：");
        PrintArray(nums2, result2_2);

        #endregion
    }

    #region 答案

    // 方法一：头部双指针法
    // 遍历整个数组，并在每次fast遇到不等于目标值的元素时，将其放置在 slow 指针的位置，最终得到移除目标值后的数组和新数组的长度。
    static int RemoveElement1(int[] nums, int val)
    {
        // 初始化两个指针，一个用于慢速遍历（slow），一个用于快速遍历（fast）
        int slow = 0;
        int fast = 0;

        // 当快速指针没有遍历完整个数组时执行循环
        while (fast < nums.Length)
        {
            // 如果快速指针指向的元素不等于目标值
            if (nums[fast] != val)
            {
                // 将慢速指针指向的位置更新为快速指针指向的元素
                // 假如slow和fast一致其实就自己赋值自己 没有关系
                // 不一致说明遇到目标值了 slow移动慢了 让fast发现不是目标值就填入
                nums[slow] = nums[fast];
                // 移动慢速指针到下一个位置
                ++slow;
            }

            // 移动快速指针到下一个位置
            ++fast;
        }

        // 返回新数组的长度，即不包含目标值的部分
        return slow;
    }

    // 方法二：首尾双指针法
    static int RemoveElement2(int[] nums, int val)
    {
        // 初始化两个指针，一个用于慢速遍历（slow），一个用于快速遍历（fast）
        int slow = 0;
        int fast = nums.Length - 1;

        // 当慢速指针小于等于快速指针时执行循环
        while (slow <= fast)
        {
            // 如果慢速指针指向的元素等于目标值
            if (nums[slow] == val)
            {
                // 如果快速指针指向的元素不等于目标值
                if (nums[fast] != val)
                {
                    // 将慢速指针指向的位置更新为快速指针指向的元素
                    nums[slow] = nums[fast];
                    // 移动慢速指针到下一个位置
                    ++slow;
                    // 移动快速指针到前一个位置
                    --fast;
                }
                else
                {
                    // 如果快速指针指向的元素也等于目标值，只移动快速指针到前一个位置
                    --fast;
                }
            }
            else
            {
                // 如果慢速指针指向的元素不等于目标值，直接移动慢速指针到下一个位置
                ++slow;
            }
        }

        // 返回新数组的长度，即不包含目标值的部分
        return slow;
    }

    

    // 打印数组前 len 个元素
    static void PrintArray(int[] nums, int len)
    {
        for (int i = 0; i < len; i++)
        {
            Console.Write($"{nums[i]} ");
        }

        Console.WriteLine();
    }

    #endregion
}

27.4 运行结果

示例1 方法1 输出长度：2
示例1 方法1 输出数组：2 2 
示例1 方法2 输出长度：3
示例1 方法2 输出数组：2 2 2 
示例2 方法1 输出长度：5
示例2 方法1 输出数组：0 1 3 0 4 
示例2 方法2 输出长度：7
示例2 方法2 输出数组：0 1 3 0 4 0 4
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏