双指针解决移除数组元素的问题

第一题 

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]

输入：nums = [1,1,2]
输出：2, nums = [1,2]

来源：力扣（LeetCode）

我们的解题思路是利用双指针来解决这个问题

我们定义两个变量一个P，一个Q

我们令P指向数组的第一个元素，令Q指向数组的第二个元素

那么当两个元素相等的时候我们令Q指针向后移动一位而P指针不动

当两个元素不相等的时候我们令此时的Q指针指向的元素等于P+1指针所指向的位置

复制完毕以后我们移动向前移动P的位置

我们用图来解释就是这样的

我们同时用P来计数，由于此时P指向4，同时我们让P的值也变成4

这样我们在输出数组的时候就可以不用理会超出P值后面的元素了

最后我们上代码

class Solution {
    public int removeDuplicates(int[] nums) {
        int p = 0;
        int q = 1;
        while (q < nums.length){
            if (nums[p] != nums[q]){
                nums[p+1] = nums[q];
                p++;
            }
            q++;
        }
        return p+1; //由于我们给P设的值为0，所以我们要手动加一
    }
}

 第二题

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

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

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

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]

来源：力扣（LeetCode）

我们的解题思路还是利用双指针来解题

只不过这一次利用的的双指针首先是指向同一个位置

定义一个P和一个Q

我们先指定Q向后移动

当Q移动到指定删除的值时，我们让Q跳过当前元素，指向后一位置的元素

不断重复直到将不是指定删除元素的值赋值给P

然后让P向后移动一位

当P没有遇到指定删除的值时，那么让P向后移动一位

用图解的方式来解释

 

最后我们上代码 

class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int left = 0;
        int right;
        for (right = 0;right < nums.length;right++){
            if (nums[right] != val){
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
}

我们还有一种思路也是利用双指针

只不过这时候的双指针指向最左和最右

当我们左边的指针指向的元素是指定删除的元素的时候

我们让右边的元素赋值给左边的指针

然后让右指针向后移动一位

当左边的指针指向的元素不是指定删除的元素的时候

我们就让左边的指针向前移动一位

最后我们上代码

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
}