leetcode刷题记录-【26 Remove Duplicates from Sorted Array】

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

划重点：1.排序数组 2.原地删除

错误思路：

1.声明一个tmp，初始就是nums[0]，用作被比较的对象

2.用tmp去和每一个后面的数去对比，相同的跳过，不同的，先把nums[j]设成tmp,然后j++，tmp变成不同的那个数

错误点：

1.使用了新的内存空间，是错误的

2.tmp要和后面的数去比，tmp如果走到了最后一个，那么后面必然会产生越界。

3.tmp最后一定是一个和前面不同的数，这个数不参与比较，那么一定不会被覆盖写入数组

比如{1,1,2,2,3,3}->{1,2,2,2,3,3}

public static int removeDuplicates(int[] nums)
{
    int i = 0, j = 0;
    int tmp = nums[0];
    for(i = 1; i < nums.length; i++)
    {
        if(nums[i] == tmp)
        {
            continue;
        }
        else
        {
            nums[j] = tmp;
            tmp = nums[i];
            j++;
        }
    }
    System.out.println(j+1);
    return j+1;
}

思路：

要求原地删除，那么一定使用快慢指针进行元素的覆盖操作。

声明两个指针，i为快指针，j为慢指针

如果遇到相同的数，那么就跳过，i++。

如果遇到不同的数，将这个值的下一个数给替换成这个不一样的值。

public static int removeDuplicates(int[] nums)
{
    int i = 0, j = 0;
    for(i = 1; i < nums.length; i++)
    {
        if(nums[j] == nums[i])
        {
            continue;
        }
        else
        {
            j++;
            nums[j] = nums[i];
        }

    }
    System.out.println(j+1);
    return j+1;
}

代码写的不够优雅，因为判断相等然后continue是没有必要的，优化一下：

public static int removeDuplicates(int[] nums)
{
    int j = 0;
    for(int i = 1; i < nums.length; i++)
    {
        if(nums[j] != nums[i])
        {
            j++;
            nums[j] = nums[i];
        }

    }
    return j+1;
}

复杂度分析：

遍历一遍，时间复杂度o(n)

空间复杂度，o(1)