算法训练营第二天| 27. 移除元素

一、今日学习任务今日任务27. 移除元素题目建议暴力的解法可以锻炼一下我们的代码实现能力建议先把暴力写法写一遍。 双指针法是本题的精髓今日需要掌握至于拓展题目可以先不看。题目链接https://leetcode.cn/problems/remove-element/视频讲解https://www.bilibili.com/video/BV12A4y1Z7LP二、自己看到题目的第一想法题目要求原地移除等于 val 的元素返回剩余元素个数。第一反应是遍历数组遇到等于 val 的元素就删掉后面的元素往前移。但这样每次删除都要移动后续元素时间复杂度高。想到可以用双指针法一个指针遍历一个指针记录存放位置。三、实现过程中遇到哪些困难1、暴力解法边界问题删除元素后数组长度变短循环变量需要回退一位否则会跳过下一个待检查元素。2、双指针理解刚开始没想清楚快慢指针各自的作用后来才明白快指针遍历原数组慢指针指向新数组的末尾位置。3、元素顺序变化题目允许顺序改变双指针法恰好利用这一点把不等于 val 的元素往前放。四、代码是怎么实现的方法一、暴力解法双重循环思路遍历数组找到等于 val 的元素后将后面的所有元素往前移动一位覆盖它同时数组长度减1循环变量回退一位继续检查。class Solution { public: int removeElement(vectorint nums, int val) { int len nums.size(); for (int i 0; i len; i) { if (nums[i] val) { // 将后面的元素前移 for (int j i; j len - 1; j) { nums[j] nums[j 1]; } i--; // 回退检查移过来的新元素 len--; // 长度减1 } } return len; } };方法二、双指针法快慢指针思路快指针 fast 遍历原数组每个元素慢指针 slow 指向新数组下一个要存放的位置。当 fast 指向的元素不等于 val 时把它放到 slow 位置slow 后移一位。最终 slow 是新数组的长度。class Solution { public: int removeElement(vectorint nums, int val) { int slow 0; for (int fast 0; fast nums.size(); fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; slow; } } return slow; } };五、今日收获心得双指针法本质快指针负责探路慢指针负责记录有效元素的位置。暴力法也有价值写一遍能加深对数组元素移动过程的理解。题目允许顺序改变可以放心覆盖不需要考虑相对顺序。原地操作不用开辟新数组直接在原数组上修改节省空间。