[Leetcode]26. Remove Duplicates from Sorted Array

题目描述

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

例子

例子 1

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn’t matter what you leave beyond the returned length.

例子 2

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn’t matter what values are set beyond the returned length.

解题思路

因为数组是排序过的，所以思路比较清晰。通过快慢指针，快指针扫描一遍数组。遇到和前一位不同的数字则通过慢指针复制，最后通过慢指针返回指定数组的长度即可，代码如下：

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;

    int slow = 0, fast = 0;
    for (fast = 1; fast < nums.size(); fast++) {
        if (nums[fast] != nums[fast - 1]) {
            nums[++slow] = nums[fast];
        }
    }

    return slow + 1;
}

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