乐趣区

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)

退出移动版