每天一题LeetCode【第12天】

T26. Remove Duplicates from Sorted Array【Easy】

题目

给一个排好序的数组,删除重复的数字，使得每个数字只能出现一次，并返回新的长度。

不要为另一个数组分配额外的空间（感觉就是不要新建数组），必须要用常数储存器来完成这个算法。

思路

① 这类题目数组开头和结尾的处理是很重要也很容易漏掉的，当输入的数组为空，也就是 length==0 时，不用进行删除，直接返回 0

② 如果能用新的数组，由于是排好序的，就比较好解决了，只要从前往后搜索碰到重复的跳过，不重复的按次序添加到新数组就好

③ 但是由于不能用额外的数组，那就只能在原数组上改动，然后由于是排好序的，所以前面的搜索过去的就没用了而且新数组长度一定小于原来的数组，所以遍历过的空间就可以看做是新数组来用了，这就解决了问题。

④ 具体可以看代码以及注释

代码

代码取自 Top Solution，稍作注释

    public int removeDuplicates(int[] nums) {
    //当length为0时，直接返回0
    if (nums.length==0) return 0;
    //初始化长度为 0
    int j=0;
    //for循环
    for (int i=0; i<nums.length; i++)
        //通过比较nums[i]和nums[j]是否有差别，然后往数组里添加
        if (nums[i]!=nums[j]) nums[++j]=nums[i];
    //+1以后返回
    return ++j;
    }

补充

i++ 和 ++i 的区别：

如果单单执行 i++ 和 ++i 结果是没啥差别的，相当于 i=i+1

当作为返回值时，i++ 是返回 i，再加 1，++i 是先加 1 再返回

一直觉得例子是最好的理解方式，举个例子吧：

① a=i++; 
  相当于：a=i; i=i+1;
② a=++i; 
  相当于：i=i+1; a=i;