代码训练(3)LeetCode之移除元素

Author: Once Day Date: 2024年3月6日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

• 27. 移除元素 - 力扣（LeetCode）
• 力扣 (LeetCode) 全球极客挚爱的技术成长平台

1. 原题

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

比如对于nums = [4, 6 , 7, 4]，且val = 4，返回nums=[4, 4, x, x], return 2，最终两个数字是什么并不重要。

2. 分析

该问题是一个简单的编程题目，用C语言来实现，只要要求性能较高(速度90%)，内存总是不会太高，因为原地修改。

首先，设想有一个装满不同小球的箱子，现在任务是把所有红色小球都拿出来。编程题目也是类似的，这个数组nums就像是这个箱子，而val就好比是红色小球，我们需要做的就是把所有val从数组nums中移除，并告诉别人最后箱子里还剩下多少个小球（即数组中剩余元素的个数）。

解题思路很简单，从数组的第一个元素开始，一直检查到最后一个元素，当你找到一个val时，你可以将它和数组最后一个元素交换，然后“丢弃”掉最后一个元素。这样，你就在不增加额外空间的情况下，原地修改了数组。重复这个过程，直到你检查完所有的元素。

分析步骤如下：

1. 初始化两个指针，一个用于遍历数组(i)，另一个用于记录非val元素的位置(length)。
2. 当遍历指针i小于数组长度时，进行循环。
3. 如果当前元素不等于val，我们就将其移动到length指定的位置，并将length加一。
4. 如果等于val，我们就跳过它，继续检查下一个元素。
5. 最后，length就是数组中非val元素的个数。

这里有个小例子：
假设nums = [3, 2, 2, 3]，val = 3。开始时length = 0，我们逐个检查元素：

• 第一个元素是3，等于val，跳过。
• 第二个元素是2，不等于val，复制到nums[0]，length变成1。
• 第三个元素是2，不等于val，复制到nums[1]，length变成2。
• 第四个元素是3，等于val，跳过。

所以，新的数组是[2, 2, 2, 3]，新长度是2。

性能优化关键点：

• 限制循环次数：只遍历一次数组。
• 减少操作：当元素等于val时，跳过而不是交换，这样可以减少不必要的操作。

3. 代码实现

int removeElement(int* nums, int numsSize, int val) {
    int remain_num = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != val) {
            if (i != remain_num) {
                nums[remain_num] = nums[i];
            }
            remain_num++;
        }
    }
    return remain_num;
}

这段代码的作用是从一个整数数组中移除所有等于给定值 val 的元素，同时保持数组其他元素的顺序不变，并返回数组中移除指定元素后剩余元素的新长度。这个操作是在原数组上进行的，不需要使用额外的空间。函数执行结束后，数组中的前 remain_num 个元素是那些不等于 val 的元素，而 remain_num 是数组中剩余（未被移除）元素的数量。

运行结果如下所示，达到了预期性能目标，基本没有申请内存，但是随机性太多，仅供参考。

4. 总结

在面对这类数组操作问题时，能力考查的焦点通常集中在对算法的理解、编程语言的熟悉程度以及代码优化的能力上。原地修改数组意味着不能简单通过创建新数组来过滤掉不需要的元素，这就需要程序员有较强的逻辑思维能力和对语言操作数组的熟练掌握。解决这个问题，需要使用双指针技巧，其中一个指针用于遍历数组，另一个指针用于记录不等于 val 的元素应该存放的位置。

从个人提升角度来看，解决这个问题可以帮助程序员加深对数组操作的理解，提高解决类似问题的速度，尤其是在面对需要优化空间和时间复杂度的问题时。在实际工作中，这种能力是非常重要的，因为它直接关系到程序的性能和资源使用效率。

操作的理解，提高解决类似问题的速度，尤其是在面对需要优化空间和时间复杂度的问题时。在实际工作中，这种能力是非常重要的，因为它直接关系到程序的性能和资源使用效率。

Once Day

也信美人终作土，不堪幽梦太匆匆......

如果这篇文章为您带来了帮助或启发，不妨点个赞👍和关注，再加上一个小小的收藏⭐！

(｡◕‿◕｡)感谢您的阅读与支持~~~