题目描述

链接: 27. 移除元素

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

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

题目分析

• 题型一维数组原地移除元素
• 关键双指针法
  • 【指针1号】从数组头开始遍历查找。
  • 【指针2号】从数组头开始控制数组不出现target。
    这个指针坚持被叫作慢指针是因为走的慢但是关键是理解好它的作用是什么
• "奇葩"理解~

不得不说这种理解真的很奇葩但是真的很形象是我偶然一次在blink上看到的虽然现在找不到那位同学了如果你能看见在这里给你表示感谢我下面用图画和语言的形式来展现一下

 对应关系

• 一串排列有序的萝卜坑&萝卜→数组&数组元素
• 橙色萝卜→“新”数组元素即不被移除元素
• 红色萝卜→需被移除元素
• 夫妻二人→双指针
  • 女生快指针
  • 男生慢指针

 过程解析

 女生负责从一厢萝卜菜地的这头视察到那头for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) 。
 男生负责挖坑nums[slowIndex++] 。
 如果遇到了橙色萝卜女生会告诉男生“把这个萝卜填到你挖的坑里面去并且继续挖下个坑可能还有橙色萝卜需要填”nums[slowIndex++] = nums[fastIndex]。
 遇到了红色萝卜她什么也不说直接跳过去寻找下一个橙色萝卜if (nums[fastIndex] == val) { continue;//快指针遇到目标元素即跳过 }。
  如此进行下去直到一厢菜地被视察完。

代码实现

class Solution {
    public int removeElement(int[] nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] == val) {
                continue;//快指针遇到目标元素即跳过
            }
            nums[slowIndex++] = nums[fastIndex];//满指针指向正确元素的正确位置
        }
        return slowIndex;
    }
}

• 时间复杂度O(n)
• 空间复杂度O(1)

补充训练–验证

如果你还是对上面的理解将信将疑不如看看下面这题验证以上理解确实有用

26. 删除有序数组中的重复项
给你一个 升序排列 的数组 nums 请你 原地 删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度所以必须将结果放在数组nums的第一部分。更规范地说如果在删除重复项之后有 k 个元素那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

代码实现

class Solution {
    public int removeDuplicates(int[] nums) {
        int slowIndex = 0;
        for (int quickIndex = 0; quickIndex < nums.length; quickIndex++) {
            //如果在遍历时发现此元素和前面重复直接跳过此元素
            if (quickIndex > 0 && nums[quickIndex] == nums[quickIndex - 1]) {
                continue;
            }
            //慢指针在后面“挖坑”等着接收
            nums[slowIndex++] = nums[quickIndex];
        }
        return slowIndex;
    }
}

write in the end:
后续还会更新很多双指针题目来加深对双指针的理解还不快快关注[笔芯]

• 专栏系列文章
  【Leetcode每日一题】69. x 的平方根/Sqrt(x)|二分查找
  【Leetcode每日一题】34.在排序数组中查找元素的第一个和最后一 个位置|二分求下标
  【Leetcode每日一题】35.搜素插入位置|二分查找数组下标
• 建立此专栏的初衷是为了监督自己每天认真刷一个题积少成多。并把自己每次刷题的思路、收获以博文的形式分享出来帮助更多人以及方便后续复习。如果有兴趣的同学可以订阅此专栏我们一起刷题一起交流进步和学习专栏LeetCode每日一题–进击大厂