(1条消息) 丝滑！数组元素的原地移除!

01、题目分析

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

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

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

示例 1:

给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

这道题比较简单哦，只要把握好“原地删除”这个关键字，就可以顺利求解啦！

具体过程如下图所示：

根据分析，我们可以得到下面的题解：

//GO
func removeElement(nums []int, val int) int {
    for i := 0; i < len(nums);{
        if nums[i] == val {
            nums = append(nums[:i],nums[i+1:]...)
        }else{
            i++
        }
    }
    return len(nums)
}

java中，可以将定一个新变量j=nums.length，当当前值等于目标值时，使用nums[i]=nums[j-1];j--实现类似go语言中的移除目标值操作，这样可以给出java题解：

//JAVA
class Solution {
    public int removeElement(int[] nums, int val) {
        int j = nums.length;
        int i = 0;
        while (i < j) {
            if (nums[i] == val) {
                nums[i] = nums[j-1];
                j--;
            } else {
                i++;
            }
        }
        return j;
    }
}

和这道题类似的还有LeetCode 26题，大家可以尝试自己先做一做，然后再看答案哦。

02、类似题目分析

题目26：删除排序数组中的重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次。

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

示例 1:

给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

这道题的重点是原地两个字，也就是要求必须在O(1)的空间下完成。并且题中已经告知了数组为有序数组，这样重复的元素一定是连在一起的，我们只需要一个一个移除重复的元素即可，具体方案方案怎么做，我们看看下面就会明白了。

移除的具体过程：

根据分析，我们可以得到下面的题解：

//GO
func removeDuplicates(nums []int) int {
    for i := 0; i+1 < len(nums);{
        if nums[i] == nums[i+1]{
            nums = append(nums[:i],nums[i+1:]...)
        }else{
            i++
        }
    }
    return len(nums)
}

在java中，没有切片的概念怎么做呢?
可以这样实现:

根据分析，我们可以得到下面的题解：

//JAVA
class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        int j = 1;
        while (j < nums.length) {
            if (nums[i] == nums[j]) {
                j++;
            } else {
                nums[i+1] = nums[j];
                i++;
                j++;
            }
        }
        return i+1;
    }
}

好啦，关于数组原地操作的两道题就讲到这里啦，如果大家有兴趣的话，可以参考做一下LeetCode 283题（移动O），也是一样的做法哦！

我把我写的所有题解都整理成了一本电子书，每道题都配有完整图解。点击即可下载

赞 (0)

相关推荐