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

发表于 分类于 阅读次数：

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

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组 nums 的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1：

1
2
3
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

1
2
3
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4,_,_,_,_,_]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

解题思路

这是一道经典的双指针题目，考察数组的原地操作。

核心思想

  • 使用双指针，一个指针指向当前不重复的位置
  • 另一个指针遍历数组寻找不同的元素
  • 将不同的元素放到前面

方法一：双指针解法（推荐）

时间复杂度 O(n)、空间复杂度 O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    if (nums.length === 0) return 0;
    
    let slow = 0; // 指向当前不重复的位置
    
    for (let fast = 1; fast < nums.length; fast++) {
        // 如果找到不同的元素，将其放到slow+1的位置
        if (nums[fast] !== nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    
    return slow + 1;
};

方法二：优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
var removeDuplicates = function(nums) {
    if (nums.length <= 1) return nums.length;
    
    let i = 0;
    for (let j = 1; j < nums.length; j++) {
        if (nums[j] !== nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    
    return i + 1;
};

方法三：使用Set（不符合要求，但思路清晰）

1
2
3
4
5
6
7
8
9
10
11
var removeDuplicates = function(nums) {
    const uniqueSet = new Set(nums);
    const uniqueArray = Array.from(uniqueSet);
    
    // 将结果复制回原数组
    for (let i = 0; i < uniqueArray.length; i++) {
        nums[i] = uniqueArray[i];
    }
    
    return uniqueArray.length;
};

解题要点

  1. 原地操作：不能使用额外空间，必须原地修改数组
  2. 双指针技巧：使用快慢指针，快指针遍历，慢指针记录位置
  3. 边界处理：空数组和只有一个元素的情况
  4. 相对顺序：保持元素的相对顺序不变

面试要点

  • 高频考点：这道题是面试中的高频题目
  • 原地操作：考察对数组原地操作的理解
  • 双指针应用：双指针的经典应用场景
  • 空间复杂度：要求O(1)空间复杂度

相关题目

扩展思考

  1. 为什么使用双指针？

    • 快指针遍历数组寻找不同元素
    • 慢指针记录当前不重复的位置

  2. 时间复杂度分析

    • 只需要遍历一次数组：O(n)
    • 空间复杂度：O(1)

  3. 边界情况

    • 空数组：返回0
    • 只有一个元素：返回1
    • 所有元素相同：返回1

  4. 算法正确性

    • 保证相对顺序不变
    • 原地修改数组
    • 返回正确的长度

最后更新: 2021-09-05