26. 删除有序数组中的重复项【LeetCode 刷题日记】

记录自己从零开始刷 LeetCode，提高自己的数据结构与算法能力，为了获得更好的工作机会

数组 简单

题目：26. 删除有序数组中的重复项
地址：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/?envType=study-plan-v2&envId=top-interview-150

解题情况

• 自行解出，暴力解法
• 先 for 循环遍历，然后把不重复的元素放进一个新数组，再遍历新数组，依次覆盖前面数组的对应元素

我的解答

• 解法：暴力解法，双重 for 循环
• 时间复杂度：O(n^2)，原数组 for 循环 n 次，新数组最大长度为 n， n * n
• 空间复杂度：O(n)，建立了一个新数组，最大长度为 n

var removeDuplicates = function (nums) {
  let _list = [];

  for (let i = 0; i < nums.length; i++) {
    if (_list && _list.findIndex((data) => nums[i] === data) === -1) {
      _list.push(nums[i]);
    }
  }

  for (let j = 0; j < _list.length; j++) {
    nums[j] = _list[j];
  }
  return _list.length;
};

参考优秀题解

• 解法：双指针
• 时间复杂度：O(n)，最多遍历数组长度 n
• 空间复杂度：O(1)，未使用额外空间
• 思考：关键点为有序，所以可以直接比较邻近 2 个元素；同理如何不是有序数组，则可以先利用 sort 进行排序，再比较邻近元素即可

var removeDuplicates = function (nums) {
  // 空数组情况
  if (nums.length === 0) {
    return 0;
  }

  // fast 遍历整个数组；slow 记录当前比对的最后索引
  let fast = 1,
    slow = 1;
  // 知道循环结束条件用 while 循环
  while (fast < nums.length) {
    if (nums[fast - 1] !== nums[fast]) {
      // 邻近元素不同，更新数组 slow 位置元素
      nums[slow] = nums[fast];
      slow++;
    }
    // 不管是否相同，fast 一直要走
    fast++;
  }
  return slow;
};

复盘

• 我现在做了 5 道数组题目了，第一反应能想到的还是暴力解法，for 循环等
• 不过这道题目是我自己独立做出来的，还是挺开心的，虽然算法效率不高
• 其实昨天我好像也做了这个题目，当初没有做出来，今天一来就做出来了，这个也是很大的进步，加油
• 几年前我最开始做 LeetCode 的时候，看到题目就感觉很烦，感觉题目读不懂，就不想做了，这次我要坚持下去，踏踏实实的做没道题，然后学习别人优秀的解法，提高自己的能力
• 最近做的这几道数组题目，我发现双指针是比较常用的解法，我需要整理归纳题型解法，做到举一反三的思维
• 我打算题目类型 5 道题为一个小阶段，然后再做其他类型的，保证每个类型都接触到，现在数组类型暂时做了 5 道了，接下来去做双指针类型题目