题号：26
难度：Easy
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array

思路

要求是在原地修改数组，故需要两个指针。

一是指向当前第一个可插入位置，即保证不重复、连续且保持原有次序的子数组的尾部。二是遍历位置的指针。

要明确，首可插入位置只在最初是不确定的，后续+1即可，所以写两个for循环。

第一个for是为找到首可插入位。第二个for是为整理数组。

另外，还要记录当前的“基准”元素，已经最后返回的数组长度。

代码

#include <vector>

using std::vector;

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        //原数组长度oriLen
        int oriLen = nums.size();
        //如oriLen为0或1，直接返回
        if(oriLen<2>) return oriLen;

        //首个可插入位firstBlankPos，初值-1，表示无
        int firstBlankPos=-1;
        //当前重复对比元素dupElem，初值nums[0]
        int dupElem=nums[0];

        //第一个for，找第一个重复元素
        //找到后将首可插入位置为该位
        //记录位置
        for(int i=1;i<oriLen;++i){
            if(nums[i]==dupElem){
                firstBlankPos=i;
                break;
            }
            else{
                dupElem=nums[i];
            }
        }
        //找不到，说明无重复
        if(firstBlankPos==-1) return oriLen;

        //找到了，继续
        for(int j=firstBlankPos+1;j<oriLen;++j){
            if(nums[j]!=dupElem){
                nums[++firstBlankPos]=nums[j];
                dupElem=nums[j];
            }
        }
        return firstBlankPos;
    }
};

提交结果

时间、空间上都还不错。

dalao解法

我还是想复杂了，这位写的简洁多了：

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

主要问题在于，没必要将“基准”元素单独存放，直接将头部子数组视作处理完的数组，则其尾元素就是待比较元素。