remove-duplicates-from-sorted-array

Remove Duplicates from Sorted Array – LeetCode 26

Problem

Description

Given a sorted array, 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 in place with constant memory.

Example

Given input array nums = [1,1,2],

Note: 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 new length.

Answer

Orignal

Code

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        unsigned size = nums.size(), result = 1;
        if(size == 0) return 0;
        int last = nums[0];
        for(int i = 1; i != nums.size(); ++i){
            int tmp = nums[i];
            if(last != tmp){
                nums[result] = tmp;
                ++result;
                last = tmp;
            }
        }
        return result;
    }
};

思路

要求对已排序的数列进行去重并返回长度，基础思路就是遍历，缓存上一个值和下一个做比较，一旦发现不同的就替换上一个重复的数字。相当与官方解的双指针法，网上的思路也都是这样。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$26$ ms，排名$33.76\%$

Better

思路

虽然还没看到更好的思路，不过在不限制空间复杂度的情况下可以使用STL中的Set来去重，可以大大简化代码。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$32$ ms，排名$64.67\%$。

Code

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
		set<int> result(nums.begin(),nums.end());
		copy(result.begin(),result.end(),nums.begin());
		return result.size();
    }
};