删除排序数组中的重复项

题目

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

个人方法

  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 ≤ 2count=0,这段区间的 num[i] 不需要移动,而 i=3 时,num[i]等于num[i-1],此时 count应该+1i=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 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!