LEETCODE刷题记录【27 Remove Element】

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

内容简介:给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。

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

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

1.先来写一个最简单的版本,即使用额外空间作为辅助,把符合条件的元素写到一个新的数组里。

public static ArrayList removeElement(int[] nums, int val)
{

    ArrayList<Integer> newNums = new ArrayList<Integer>();
    for (int item:nums)
    {
        if(item != val)
        {
            newNums.add(item);
        }
    }
    System.out.print(newNums.size());
    return newNums;
}

基础知识查漏补缺:

1.Java数组的声明、初始化和使用

遇到了一个问题,新的数组需要声明和初始化,但是新数组的长度还不知道,怎么初始化。

考虑使用ArrayList

2.ArrayList的声明和使用

3.静态方法中调用非静态方法的限制

上述方法:

1.需要遍历数组一次,所以时间复杂度是o(n)

2.需要使用一个数组作为额外空间,所以空间复杂度是o(n)

2.还有没有优化空间?

进阶版本--降低空间复杂度

思路:

方法1需要开辟一个新的数组空间,然而题目中给定的说明,不需要考虑数组中超出长度后面的元素,可以考虑把旧数组的空间再利用。

由于必须要根据索引替换数组的值,所以不能用For-Each循环方法。

public static int removeElement(int[] nums, int val)
{
    int j = 0;
    for (int i = 0;i < nums.length;i++)
    {
        if(nums[i] != val)
        {
            nums[j] = nums[i];
            j++;
        }
    }
    System.out.print(j);
    return j;
}

复杂度分析:

时间复杂度:o(n) 遍历2n次

空间复杂度:o(1)

3.还有没有优化空间?

方法2在某些特定场景下会进行不必要的复制操作,影响性能。比如{1,2,3,5,4} val=4,或者{4,1,2,3,5},似乎没有必要把前4个元素复制一遍,在这一点上可以进行优化,优化思路为如果匹配到需要剔除的元素,就把数组末尾的元素替换到这个位置来。注意:尾部的元素有可能是需要剔除的,所以,下一轮循环要从当前索引重新开始。

public static int removeElement(int[] nums, int val)
{
    int n = nums.length;
    System.out.print(n);
    for (int i = 0;i < n;i++)
    {
        if(nums[i] == val)
        {
            nums[i] = nums[n-1];
            i--;
            n--;
            System.out.println("1:n--:"+n);
        }
    }
    System.out.print(n);
    return n;
}

遇到的问题:

1.在循环里,把nums.length作为了固定长度,会导致所有元素都被遍历,实际上被替换到前面的元素不需要被遍历,导致了bug

2.在使用i--时,考虑如果数组前几个元素都是需要被剔除的元素,会不会导致index为负,导致溢出。经过分析和实验不会,因为每次循环结束i都要++

复杂度分析:

时间复杂度:o(n) 遍历n次

空间复杂度:o(1)

总结:

1.学会的新方法,双指针法

2.如果没有普遍的优化方法,那么就考虑业务场景的特点,比如方法三,针对某些特殊场景提出优化空间。


以上所述就是小编给大家介绍的《LEETCODE刷题记录【27 Remove Element】》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

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

算法心得:高效算法的奥秘(原书第2版)

算法心得:高效算法的奥秘(原书第2版)

(美)Henry S. Warren, Jr. / 爱飞翔 / 机械工业出版社 / 2014-3 / 89.00

【编辑推荐】 由在IBM工作50余年的资深计算机专家撰写,Amazon全五星评价,算法领域最有影响力的著作之一 Google公司首席架构师、Jolt大奖得主Hoshua Bloch和Emacs合作创始人、C语言畅销书作者Guy Steele倾情推荐 算法的艺术和数学的智慧在本书中得到了完美体现,书中总结了大量高效、优雅和奇妙的算法,并从数学角度剖析了其背后的原理 【读者评价......一起来看看 《算法心得:高效算法的奥秘(原书第2版)》 这本书的介绍吧!

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

HTML 编码/解码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具