LeetCode(26)删除有序数组中的重复项

如果说面试中小呆最怕什么，那一定是算法。在以往的业务开发中，遇到需要算法的地方屈指可数。加上大学期间并没有系统的学过数据结构与算法，导致算法成为了小呆的一个非常明显的短板。曾经有一段时间突击过数据结构与算法的学习，遗憾的是并没有坚持下来。从今天开始，重新开启每日一题，旨在弥补短板，成为更好的自己。

今天是小呆刷题的第1天，今天的题目是：力扣（LeetCode)的第26题，删除有序数组中的重复项

题目要求

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

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有k个元素，那么nums的前k个元素应该保存最终结果。

将最终结果插入nums的前k个位置后返回k。

不要使用额外的空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。

示例：

1
2
3

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

提示：

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列

解题思路

由于数组已经按升序排列，那么相同的元素一定是相邻的。我们可以使用双指针算法来解这道题。

设定一快一慢两个指针，让他们指向数组的起始位置（下标0）
快指针在前面跑，遇到值与慢指针不一样，就让慢指针前进一步，同时替换为快指针的值
当数组遍历完，就得到了想要的结果

为了方便理解，小呆制作了一个gif图，展示了每一次循环过程中两个指针的移动过程和值修改的过程。对比下列代码更容易理解。

快慢指针

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    if(nums.length === 0) { // 判断边界值，如果数组为空，直接返回0
        return 0
    }
    let fast = 0, slow = 0 // 设定快慢2个指针
    while(fast < nums.length) {
        if(nums[fast] !== nums[slow]) { // 当快指针的值与慢指针的值不相等时
            slow++ // 让慢指针往前移一位
            nums[slow] = nums[fast] // 将慢指针的值替换为快指针的值
        }
        fast++
    }
    return slow + 1  // 由于返回的是数组的新长度，所以需要+1（数组下标从0开始）
}