# Remove Duplicates from Sorted Array

## Remove Duplicates from Sorted Array

原题链接：<https://leetcode.com/problems/remove-duplicates-from-sorted-array/>

### 描述

> Given a sorted array *nums*, remove the duplicates [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) 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**](https://en.wikipedia.org/wiki/In-place_algorithm) with O(1) extra memory.

### 例子

> 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.

* 注意

> Note that the input array is passed in by **reference**, which means modification to the input array will be known to the caller as well.

### 解法一

使用index，在原数组上做remove

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

或者

```cpp
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int index = 0;
        int n=nums.size();
        for(int i = 1; i < n; i++){
            if(nums[i] == nums[i-1]) index++;
            else nums[i-index] = nums[i];
        }
        return n-index;
    }
};
```

**分析：**

T=O(n), S=O(1)

### 解法二

使用STL的distance和unique

**关于distance：**

[**http://cplusplus.com/reference/iterator/distance/?kw=distance**](http://cplusplus.com/reference/iterator/distance/?kw=distance)

Calculates the number of elements between first and last.

**关于unique：**

[**http://cplusplus.com/reference/algorithm/unique/?kw=unique**](http://cplusplus.com/reference/algorithm/unique/?kw=unique)

Removes all but the first element from every consecutive group of equivalent elements in the range `[first,last)`.

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

**分析：**

根据STL中unique是使用双指针实现的：

```cpp
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;
}
```

### 解法三

改写unique，使用upper\_bound

```cpp
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        return distance(nums.begin(), removeDuplicates(nums.begin(),nums.end(), nums.begin()));
    }
    template<typename InIt, typename OutIt>OutIt removeDuplicates(InIt first, InIt last, OutIt output) {
        while (first != last) {
            *output++ = *first;
            first = upper_bound(first, last, *first);
        }
        return output;
    }
};

```

**分析：**

## 总结

题目开始，联想到快慢指针的方法。如果对STL熟悉，可以想到unique函数来进行解题，但是题目提示为sorted array，所以unique的解法不一定是最优解。在理解unique的原理和分析题目的基础上，作出变形改写。