27.移除元素

LeetCode LeetCode 数组双指针

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

字数:2.8k 阅读 :

评论:

27.移除元素

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 题解

方法一：头部双指针法

思路

使用快慢两个指针从头开始遍历。快指针遍历整个数组，当遇到不等于目标值的元素时，将其放到慢指针位置，慢指针前进。这样慢指针最终指向的位置就是新数组的长度。

核心思想：慢指针指向「下一个有效元素应放置的位置」，快指针负责「发现有效元素」。

具体步骤：

初始化慢指针 slow = 0，快指针 fast = 0。
遍历数组：
- 如果 nums[fast] != val：
  - nums[slow] = nums[fast]（放到慢指针位置）
  - slow++（慢指针前进）
- fast++（快指针始终前进）
返回 slow（新数组长度）。

举例：对于 nums = [0,1,2,2,3,0,4,2], val = 2：

slow=0, fast=0：nums[0]=0 != 2，nums[0]=0，slow=1
slow=1, fast=1：nums[1]=1 != 2，nums[1]=1，slow=2
slow=2, fast=2：nums[2]=2 == 2，跳过
slow=2, fast=3：nums[3]=2 == 2，跳过
slow=2, fast=4：nums[4]=3 != 2，nums[2]=3，slow=3
slow=3, fast=5：nums[5]=0 != 2，nums[3]=0，slow=4
slow=4, fast=6：nums[6]=4 != 2，nums[4]=4，slow=5
slow=5, fast=7：nums[7]=2 == 2，跳过
返回 5，数组前 5 个元素为 [0,1,3,0,4]

复杂度分析

时间复杂度：O(n)，遍历一次数组。
空间复杂度：O(1)，只使用两个指针变量。

代码

// 方法一：头部双指针法
// 遍历整个数组，并在每次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;
}

方法二：首尾双指针法

思路

使用首尾两个指针。当首指针遇到目标值时，用尾指针指向的元素替换，然后尾指针前移。这样可以减少元素移动次数，但会改变元素的相对顺序。

核心思想：用末尾元素覆盖要删除的元素，避免移动大量元素。

具体步骤：

初始化首指针 slow = 0，尾指针 fast = nums.Length - 1。
当 slow <= fast 时：
- 如果 nums[slow] == val：
  - 如果 nums[fast] != val：用 nums[fast] 覆盖 nums[slow]，slow++
  - fast--（无论是否覆盖，尾指针都前移）
- 否则：slow++
返回 slow（新数组长度）。

举例：对于 nums = [0,1,2,2,3,0,4,2], val = 2：

slow=0, fast=7：nums[0]=0 != 2，slow=1
slow=1, fast=7：nums[1]=1 != 2，slow=2
slow=2, fast=7：nums[2]=2 == 2，nums[7]=2 == 2，fast=6
slow=2, fast=6：nums[2]=2 == 2，nums[6]=4 != 2，nums[2]=4，slow=3，fast=5
slow=3, fast=5：nums[3]=2 == 2，nums[5]=0 != 2，nums[3]=0，slow=4，fast=4
slow=4, fast=4：nums[4]=3 != 2，slow=5
返回 5，数组前 5 个元素为 [0,1,4,0,3]

复杂度分析

时间复杂度：O(n)，最多遍历一次数组。
空间复杂度：O(1)，只使用两个指针变量。

代码

// 方法二：首尾双指针法
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