博文中会简要介绍Leetcode P0026题目分析及解题思路。

“Remove Duplicates from Sorted Array”是比较简单的题目，主要难点在于控制空间复杂度在O(1)。如果没有这个要求，那么可以很简单的用HashTable来去重，然后按序来返回最终结果，但是由于要满足对空间复杂度的要求，则需要考虑如何在线性时间和常数空间内完成去重，并将所有的不同的数字前置在数组前端。

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.

这道题的思路比较直接，时间复杂度是O(n)，解法的核心思路如下：

简单来说，不存在重复副本的时候，pos和idx指针保持一致；当出现副本时，仅移动idx指针，pos保持不变。

以下是Java的题解代码实现。

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        
        int prev = nums[0];
        int pos = 1;
        for (int idx=1; idx<nums.length; ++idx) {
            nums[pos] = nums[idx];
            if (nums[pos] != nums[pos-1])
                ++pos;
            
        }
        
        return pos;
    }
}

以下是C++的题解代码实现。

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