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

栏目: 编程工具 · 发布时间: 4年前

内容简介:不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。划重点:1.排序数组 2.原地删除错误思路:

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 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)


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

论因特网

论因特网

[美] 休伯特·L.德雷福斯 / 喻向午、陈硕 / 河南大学出版社 / 2015-5 / 32.00

本书是与日俱增的关于因特网利弊之文献的重要补充。 ——《哲学评论》 关于因特网种种承诺的一次清晰辨析……以哲学家的眼光审视一个影响我们所有人的问题。 ——《普遍存在》杂志 ……一场精心设计的论战……我们需要更多德雷福斯这样的老师,将网络融入依 然具有深邃人性的课程。 ——亚当•莫顿(出自《泰晤士报文学增刊》) 在互联网世界,不管你是菜鸟,还是浸淫其中已久—......一起来看看 《论因特网》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具