题目链接

题目描述

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 0026-删除有序数组中的重复项 - 图1 额外空间的条件下完成。

示例

示例1：

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

提示

  • 0 <= nums.length <= 3 * 10
  • -10 <= nums[i] <= 10

  • nums 已按升序排列

    思路

    快慢指针

    实质上不是删除元素，而是把重复的元素移到数组后面去。

    题解

    1. class Solution {
    2.  public:
    3.   int removeDuplicates(vector<int>& nums) {
    4.       int n = nums.size();
    5.       if (0 == n) {
    6.           return 0;
    7.       }
    8.       int slow = 0;
    9.       for (int fast = 1; fast < n; ++fast) {
    10.           if (nums[fast] != nums[slow]) {
    11.               nums[++slow] = nums[fast];
    12.           }
    13.       }
    14.       return slow + 1;
    15.   }
    16. };

    复杂度分析

  • 时间复杂度：0026-删除有序数组中的重复项 - 图2

  • 空间复杂度：0026-删除有序数组中的重复项 - 图3