leetcode 26. 删除有序数组中的重复项

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

题目

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

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

示例

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

提示

• $0 <= nums.length <= 3 * 10^4$
• $-10^4 <= nums[i] <= 10^4$
• nums 已按升序排列
• 返回数组长度

  // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
  for (int i = 0; i < len; i++) {
      print(nums[i]);
  }

解一：双指针法

思路

双指针，指定两个指针slow和fast，同时扫描串
保持fast指向的值应该的slow指向的下一个值

• 相等时，slow不动，fast前进1
• 不等时，slow前进1
  • 如果前进后的slow与fast值不等，则把它赋值为fast指向的值
  • fast前进1

代码

/**
 /**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    const n=nums.length
    if(n<=1) return nums;
    let slow=0,fast=1;
    while(fast<n){
        //如果指针指向的数不相等
        if(nums[slow]!==nums[fast]){
            slow++;
            if(nums[slow]!==nums[fast]) nums[slow]=nums[fast];
        }
        fast++;
    }
    slow++;
    //题目要求返回数组长度
    return slow;
};

复杂度分析

时间复杂度$O(N)$，空间复杂度$O(1)$