Remove Duplicates from Sorted Array

编号 : 26      
难度 : <font color="green">Easy</font>

# 题目 :  
>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.
>
>**Example 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.
>
>**Example 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.
>
>**Clarification**:
>
>Confused why the returned value is an integer but your answer is an array?
>
>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.
>
>Internally you can think of this:
>
>```
>// nums is passed in by reference. (i.e., without making a copy)
>int len = removeDuplicates(nums);
>
>// any modification to nums in your function would be known by the caller.
>// using the length returned by your function, it prints the first len elements.
>for (int i = 0; i < len; i++) {
>    print(nums[i]);
>}
>```
>

# 解 :  
```Cpp
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() == 0)
        {
            return 0;
        }

        int current = nums[0];
        int count = nums.size();
        for(int i = 1; i < count; )
        {
            if(nums[i] == current)
            {
                /* 发现重复的数据，把后面的数据往前移动，覆盖掉这个值 */
                for(int j = i + 1; j < count; j++)
                {
                    nums[j - 1] = nums[j];
                }
                count--;
            }
            else
            {
                current = nums[i];
                i++;
            }
        }

        return count;
    }
};
```

# 分析 :  
这道题要求删除有序数组中重复的数值，只要将不重复的值放在数组开头并返回正确的长度即可，尾部多余的部分可以不用处理。

上述解法中从头开始搜索数组，发现重复的值，就将数组后面的部分向前移动，覆盖掉它，整体的时间复杂度是`O(n^2)`，非常慢。

## 更快的办法
没有必要在发现重复的值的时候整体移动，只需要找到**不重复**的值并提取到数组开头即可，这样做的时间复杂度是`O(n)` :  
```Cpp
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() == 0)
        {
            return 0;
        }

        int index = 1; // 指示要插入的位置
        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i] != nums[index-1])
            {
                nums[index] = nums[i];
                index += 1;
            }
        }

        return index;
    }
};
```

运行结果 :  

| 方案   | Runtime | Memory   |
| :-:    | :-:    | :-:      |
| O(n^2) | 424 ms |  10 MB   |
| O(n)   |  16 ms | 9.9 MB   |