Question

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.

For example,
Given input array 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 new length.

Solution

first solution

{% codeblock [lang:C++] %}

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

{% endcodeblock %}

when I change my code into following kind, the performance optimizes a lot.

{% codeblock [lang:C++] %}

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

{% endcodeblock %}

so, next time, I'd better put return of the function as forward as possible.

second solution

using STL

{% codeblock [lang:C++] %}

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        return distance(nums.begin(),unique(nums.begin(),nums.end()));
    }
};

{% endcodeblock %}

The behavior of unique function template is equivalent to[1]:

{% codeblock [lang:C++] %}

template <class ForwardIterator>
  ForwardIterator unique (ForwardIterator first, ForwardIterator last)
{
  if (first==last) return last;

  ForwardIterator result = first;
  while (++first != last)
  {
    if (!(*result == *first))  // or: if (!pred(*result,*first)) for version (2)
      *(++result)=*first;
  }
  return ++result;
}

{% endcodeblock %}

[1]: cpp reference

原文地址：我的主页文章