带你读《图解算法小抄》十九、双指针（3）

带你读《图解算法小抄》十九、双指针（2）https://developer.aliyun.com/article/1348033?groupCode=tech_library

2.从排序数组中删除重复项

1）问题描述：

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

你不需要考虑数组中超出新长度后面的元素。

示例：

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

1. 解题步骤：
   

• 首先，我们需要确认数组是排序的。如果数组没有排序，我们需要先对其进行排序。
  
• 设置两个指针，一个快指针，一个慢指针。快指针用于遍历数组，慢指针用于标记非重复元素的最后一个位置。
  
• 当快指针遍历数组时，比较快指针和慢指针指向的元素，如果不相等，说明遇到了新的元素，将慢指针后移一位，并将快指针指向的元素值赋给慢指针。
  
• 当快指针遍历完整个数组后，慢指针的位置（加1）就是数组新的长度。
  

3）解题框架：

function removeDuplicates(nums) {
    if(nums.length == 0) return 0;
    let i = 0;
    for (let j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
}
return i + 1;
}

3.移除元素

1）问题描述：

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

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

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

示例：

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

2）解题步骤：

设置两个指针，一个快指针，一个慢指针。快指针用于遍历数组，慢指针用于标记非目标元素的最后一个位置。

当快指针遍历数组时，比较快指针指向的元素和目标值，如果不相等，说明这个元素需要保留，将慢指针后移一位，并将快指针指向的元素值赋给慢指针。

当快指针遍历完整个数组后，慢指针的位置（加1）就是数组新的长度。

3）解题框架：

function removeElement(nums, val) {
    let i = 0;
    for (let j = 0; j < nums.length; j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
return i;
}

带你读《图解算法小抄》十九、双指针（4）https://developer.aliyun.com/article/1348031?groupCode=tech_library