LEETCODE刷题记录【27 Remove Element】

马龙驹发布于2019-08-19 11:45 / 3167人阅读

摘要：复杂度分析时间复杂度遍历次空间复杂度还有没有优化空间方法在某些特定场景下会进行不必要的复制操作，影响性能。注意尾部的元素有可能是需要剔除的，所以，下一轮循环要从当前索引重新开始。

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

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

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

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

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

    ArrayList newNums = new ArrayList();
    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.如果没有普遍的优化方法，那么就考虑业务场景的特点，比如方法三，针对某些特殊场景提出优化空间。

云服务器 GPU云服务器 Element LeetCode remove LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77820.html

leetcode-27. Remove Element

摘要：题目阐释根据告知的元素，从列表中删除，并计算剩余元素的个数重点通过移动一个列表的元素，记录位置，将一个列表内的所有元素分类。题目阐释：根据告知的元素，从列表中删除，并计算剩余元素的个数重点：通过移动一个列表的元素，记录index位置，将一个列表内的所有元素分类。计算剩余元素的个数，也可以看成先分类，再统计。 Given an array nums and a value va...

cgspine 2019-07-30 17:19 评论0 收藏0
leetcode刷题记录--【80 Remove Duplicates from Sorted Ar

摘要：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。正确思路对于每一个元素，都进行移动。或者比较不到最后一个对象。给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。错误思路：由26题跳过一个的思...

haobowd 2019-08-19 11:46 评论0 收藏0
leetcode刷题记录-【26 Remove Duplicates from Sorted Ar

摘要：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用额外空间的条件下完成。声明两个指针，为快指针，为慢指针如果遇到相同的数，那么就跳过，。给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组...

heartFollower 2019-08-19 11:46 评论0 收藏0
Leetcode 27 Remove Element

摘要：同时我们将这个元素赋值给，这样就可以保证，不等于的个元素完美占据数组的前个位置。方法二当我们遇到和等于值的元素的时候，我们将数组尾端的元素和此元素交换位置。之后减少一位遍历长度。同时在下次遍历中，我们会重新检查新过来的元素。题目介绍要求输入：给定数组nums[]，数字val要求输出：数组中不等于val的元素个数n，同时要求不等于数字val的n个元素放置在数组的前n个位置（不要求顺序...

_ipo 2019-08-15 13:34 评论0 收藏0
13. 罗马数字转整数-----leetcode刷题（python解题）

摘要：题目罗马数字包含以下七种字符，，，，，和。字符数值例如，罗马数字写做，即为两个并列的。通常情况下，罗马数字中小的数字在大的数字的右边。同样地，数字表示为。给定一个罗马数字，将其转换成整数。 [TOC] 题目罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。字符数值 I 1 V 5 X ...

Gu_Yan 2019-07-31 10:38 评论0 收藏0