跳到主要内容

删除有序数组中的重复项

题目链接​

删除有序数组中的重复项

题目​

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

  • 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

思路​

  1. 初始检查：如果数组长度为1，则直接返回1。
  2. 双指针法：
    • slow指针用于记录唯一元素的位置。
    • fast指针用于遍历数组。
  3. 遍历数组：
    • 从索引1开始，fast指针遍历数组。
    • 如果fast指针指向的元素与前一个元素相同，则跳过当前元素。
    • 如果不同，则将fast指针指向的元素赋值给slow指针的下一个位置，同时递增slow指针。
  4. 返回结果：返回slow + 1，即唯一元素的数量。

解题方法​

  1. 初始化slow指针为0，用于记录唯一元素的位置。
  2. 遍历数组，从索引1开始（fast指针）。
  3. 如果fast指针指向的元素与前一个元素相同，继续下一次循环。
  4. 如果不同，则将fast指针指向的元素赋值给slow指针的下一个位置，并递增slow指针。
  5. 遍历完成后，返回slow + 1。

代码​

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
  if (nums.length === 1) {
    return 1;
  }

  // 初始化慢指针
  let slow = 0;

  // 快指针遍历数组
  for (let fast = 1; fast < nums.length; fast++) {
    // 如果当前元素与前一个元素不同
    if (nums[fast] !== nums[fast - 1]) {
      // 将当前元素赋值给慢指针的下一个位置
      nums[++slow] = nums[fast];
    }
  }

  // 返回唯一元素的数量
  return slow + 1;
};

复杂度分析​

该算法的时间复杂度为O(n)O(n)，其中n是数组的长度。原因如下：

  • 该算法使用了两个指针slow和fast，其中fast指针遍历了整个数组，执行了n次操作。
  • 每次循环中，判断条件和赋值操作都是常数时间操作（O(1)O(1)）。

因此，总的时间复杂度是O(n)O(n)，空间复杂度是O(1)O(1)。