删除排序数组中的重复项

题目

1. 链接：https://leetcode-cn.com/problems/remove-du...
2. 题面：
   

个人方法

1. 分析：

   • 给出的是已经排好序的数组，那么重复的元素肯定相邻
   • 题目中要求的是要在给出的数组上操作，而我们如果不使用深拷贝，就需要一些能操作原始数组的方法， Array.splice() 也就是此次用到的核心方法
   • 算法：遍历数组，如果第 i 项与第 i+1 项重复，那么就删除第 i 项，再用 i-- 更新下标

2. 代码：

   var removeDuplicates = function(nums) {
     // 遍历数组
     for (var i=0; i<nums.length-1; i++) {
       if (nums[i] == nums[i + 1]) {  // 若重复
         nums.splice(i,1);  // 删除第i项
         i--;  // 更新下标
       }
     }
     return nums.length;
   };

大佬启示

法一

1. 对于返回的长度，很明显，等于 原数组的长度 － 重复元素的个数

2. 对于返回的数组，由题干以及两个示例可以得出：只是重复的部分被不重复的部分所替代

   • 如，对于 [1, 2, 3, 3, 4, 5, 6, 6, 7]，经过操作后应该是 [1, 2, 3, 4, 5, 6, 7, 6, 7]，而返回的数组是前7个不重复的元素，即 [1, 2, 3, 4, 5, 6, 7]，返回的长度为7

3. 所以，算法如下：

   • 定义 count 来记录重复的元素
   • 用 i(1 ≤ i ≤ n) 循环下标来遍历原数组
     • 若 nums[i] 与 nums[i-1] 相同，则 count + 1，表示这是第几个重复的元素，
     • 若 nums[i] 与 nums[i-1] 不同，则 nums[i] 应该向前移动 count 个下标来替换 num[i-count]
   • 例如：对于 [1, 2, 3, 3, 4, 5, 6, 6, 7]，1 ≤ i ≤ 2 时 count=0，这段区间的 num[i] 不需要移动，而 i=3 时，num[i]等于num[i-1]，此时 count应该+1，i=4 时，num[i] 就应该替换 num[i-count]，也就是 num[4] 要替换 num[3]

4. 代码：

   var removeDuplicates = function(nums) {
       var count = 0;
       for(var i=1,len=nums.length; i<len; i++){
           if(nums[i] == nums[i-1])
               count ++;
           else
               nums[i-count] = nums[i]
       }
       return len-count;
   };

法二（双指针法）

1. 顾名思义，我们将会用到两个指针，分别是遍历数组的 i，和记录重复元素第一次出现位置的 r

2. 算法如下：

   • 用 i(1 ≤ i ≤ n) 遍历数组，并初始化 r=0
   • 若 nums[i]不等于nums[i-1]，则 r++且i++ ，且执行 nums[r] = num[i]（这是为了之后遇到不重复元素做铺垫），两个指针将同步循环
   • 若 nums[i]等于nums[i-1]，则 r 不变，而只是 i++，此时的 r 将记录下重复元素的首次下标
   • 因为 r 是索引值，所以最后返回的长度是 r+1

3. 代码：

   var removeDuplicates = function(nums) {
       var r = 0;
       for(var i=1,len=n.length; i<len; i++) {
           if(nums[i] != nums[i-1]) {
               r ++;
               nums[r] = nums[i]
           }
       }
       return r+1;
   }

本作品采用《CC 协议》，转载必须注明作者和本文链接