1. 首页
  2. LeetCode

每日一道 LeetCode (8):删除排序数组中的重复项和移除元素

每日一道 LeetCode (8):删除排序数组中的重复项和移除元素

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

引言

今天破例两道题,原因是我做完第一道题感觉有点简单,顺手看了下后面的那道题,发现这两道题的思路是一致的,就合在一起了。

题目:删除排序数组中的重复项

题目来源:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

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

你不需要考虑数组中超出新长度后面的元素。

解题:删除排序数组中的重复项

这道题是少有的简单题,我的这个简单题是经过思考,很轻易的就能想出解决方案。

这道题的难点其实只有一个 「不要使用额外的数组空间,必须修改原数组的条件下完成。」 。

如果没有这个限制条件,我觉得每一位刚接触编程的同学都能完成这个任务。

先说说没有限制条件的做法,直接新开一个数组,然后循环给定的数组 nums ,遇到符合条件的直接塞到新数组里面。

但是如果限制了空间使用,只能在原数组上做操作,这个就稍微有点困难了。

不过还好的是,示例里面只要求我们原数组的前 n 个元素正确就好了,后面的元素无需考虑。

给定的数组本身是有序的,那么如果数组长度只有 0 或者是 1 的时候,我们的程序是不需要做操作的,直接返回就好了,这样,第一个极限值判断条件就出来了。

接下来就是我们如何在一个数组中进行操作,将重复的值去掉了。

因为我们的目标是获取一个没有重复元素的数组,所以事情就很简单了,定义两个指针: j 和 i ,我们循环数组,开始移动 i ,只要发现 j 和 i 指向的元素不相同,就把 i 赋值给 j ,然后 ++j 后继续循环,直到循环结束。

简单画个图解释下:

每日一道 LeetCode (8):删除排序数组中的重复项和移除元素

这幅图先不解释,直接上代码:

public int removeDuplicates(int[] nums) {
    if (nums.length < 2) return nums.length;
    int j = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[j] != nums[i]) {
            nums[++j] = nums[i];
        }
    }
    return ++j;
}

每日一道 LeetCode (8):删除排序数组中的重复项和移除元素

上面图没理解的对着这段代码看,注意我里面的赋值操作,当发现 i 和 j 不一样以后,我把 i 的值赋值给了 ++j ,意思就是 j 的下一位。

好了,这个题没有其他滑头了结束了。

题目:移除元素

题目来源:https://leetcode-cn.com/problems/remove-element/

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

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

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

示例 1:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

解题:移除元素

这道题的限制和前面一道题完全一样,都是不允许开新的数组,要在原数组解决。

解题思路也和前面的一道题非常非常像,像到我都不好意思说这是两道题。

这道题的目标是找到所有的目标值,然后 「移除」 出去,实际上是把这个值扔到后面去,我们只需要保证前面的值正确就行。

思路和上面完全一致,同样是开两个指针 j 和 i ,然后开始循环数组,当遇到和目标值不一样的,我们把这个值放到 j 的位置,并且让 j 向后移动一位,直至循环结束。

上代码辅助理解:

public 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++;
        }
    }
    return j;
}

每日一道 LeetCode (8):删除排序数组中的重复项和移除元素

这两道题题我就不多做解释了,如果实在搞不懂的, debug 一下上面的代码,保证你分分钟理解清楚。

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code