26.删除有序数组中的重复项（LeetCode）

什么叫非严格递增呢？就是前一个元素小于等于后一个元素

想法一

循环遍历数组，如果该元素与前一个相同，则整体向前挪动覆盖

时间复杂度：O(N^2)   空间复杂度：O(1)  

想法二

想法一思考起来比较简单，容易想到，但是时间复杂度太高，有没有什么方法可以降低空间复杂度呢？

以空间换时间： 创建一个临时数组，创建两个指针src1和src2，一前一后，向后访问，dst指针指向临时数组，先将第一个元素拷贝到tmp数组，接着如果src1和src2相同，则src2++，跳过该元素；如果不相同，则将src1移到src2的位置上，src2++，dst++，再将src1的元素拷贝到dst指向的空间，直到src2指向空

时间复杂度：O(N)   空间复杂度：O(N)  

想法三

其实，经过想法二的铺垫，我们想到了一种更优更简洁的解法——直接在原数组操作

只用创建src1和src2两个指针即可，如果src1和src2相同，则src2++；如果不相同，则先src1++，将src2的元素拷贝到src1上，覆盖之前相同的元素，再src2++

对上图分析：开头两个0，则src2++；0和1不同，则src1++，将src2指向的1覆盖src1指向的0，再src2++；后面因为相同，连续跳过3个1，src2到2，1和2不同……以此类推

时间复杂度：O(N)   空间复杂度：O(1)  

代码如下：

int removeDuplicates(int* nums, int numsSize)
{
    int src = 1;
    int dst = 0;
    while(src < numsSize)
    {
        if(nums[dst] != nums[src])
        {
            nums[++dst] = nums[src++];
        }
        else
        {
            src++;
        }
    }
    return dst+1;
}

这里src和dest是整型变量，代表数组下标，实际上作用也是指针 ，而且返回长度更加方便