signed

QiShunwang

“诚信为本、客户至上”

26 删除有序数组中的重复项(2021-04-26 )

2021/4/26 15:23:20   来源:

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

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

题目描述见链接内容。

解法1:双指针

先做了27题,实际上应该先做这道题目。

要注意,输入的是有序数组,看了一下自己两年前做的,使用了splice方法,这也太赖了。

还是使用了双指针,idx指针的保留逻辑就是,nums[i]与当前idx指针指向值不相同,那么就将nums[i]保存到++idx位置上

var removeDuplicates = function (nums) {
  const length = nums.length;
  
  if (length === 0) {
    return 0;
  }
  
  let idx = 0;
  
  for (let i = 1; i < length; i++) {
    if (nums[i] !== nums[idx]) {
      nums[++idx] = nums[i];
    }
  }
  return idx + 1;
};
  • 时间复杂度:${O(N)}$
  • 空间复杂度:${O(1)}$
  • 执行用时:92ms, 在所有JavaScript提交中击败了89.62%的用户,内存消耗:40.2MB,在所有JavaScript提交中击败了42.62%的用户

解法2:双指针(快慢指针)

原理相同,只是理解方式不同,声明两个指针,一个fast快指针,一个slow慢指针,fast指针先行,不断与前一个位置比较,相同的话只有fast迁移,不同的话将fast对应的值赋给slow,然后两个指针同时前移

var removeDuplicates = function (nums) {
  const length = nums.length;
  if (length === 0) {
    return 0;
  }

  let fast = 1,
    slow = 1;

  while (fast < length) {
    if (nums[fast] !== nums[fast - 1]) {
      nums[slow++] = nums[fast];
    }
    fast++;
  }

  return slow;
};
  • 时间复杂度:${O(N)}$
  • 空间复杂度:${O(n)}$
  • 执行用时:84ms, 在所有JavaScript提交中击败了98.51%的用户,内存消耗:40.2MB,在所有JavaScript提交中击败了47.42%的用户

相关题目

  • 27. 移除元素
  • 80. 删除有序数组中的重复项 II