来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/remove-element
1、题目描述 先来看一下本题题目描述:
给你一个数组 nums 和一个值 val,你需要 原地移除 所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
题目比较好理解,简单来说就是在删除元素过程中不准构造新的数组。先来看看官网上的一些实例:
示例1:
输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。
2、解题思路示例2:
输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,4,0,3]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
第一种解法:暴力解法
首先的话,当然还是暴力解法,直呼yyds。先上一层for循环,毕竟删除目标元素之前得先把它在数组里面定位出来,定位出来后就是把找到的元素从数组中删除。但是,我们都知道,因为数组在内存中的地址是连续的,所以对数组进行元素删除的时候实际上是把该元素后面的所有元素向前移动一位,而这个操作就需要再进行一次for循环,只是第二次循环的数组就相当于是原来数组的子数组。
动画演示:
代码(Java):
public int removeElement(int[] nums, int val) {
//新数组长度
int length = nums.length;
//第一层for循环,定位目标元素
for(int i =0;i
有些朋友可能疑惑 i-- 操作,这里解释一下。考虑没有 i-- 操作的话,会有什么样的后果。首先,经过第二次循环体中元素前移,会导致本次遍历位置 i 上的目标元素也被新元素替换;其次,如果此时不对 i 这个位置进行更新,那么经过 i++ 操作,原来位置上的新元素就可以逃过遍历查找,导致我们的遍历不完整。因此,需要经过先减后加的操作后,原来位置上的新元素就可以遍历的到了。
第二种解法:双指针法
上述方法经过leetcode运行会超出时间限制,因此需要使用优化方法。如何找出优化方法呢?首先是我们解题过程中有哪些关键步骤,其次,这些关键步骤中的操作是否使用更加优秀的方法替代。该题共两个步骤:第一步查找目标数组中目标元素;第二步对目标元素进行删除。
上面的方法中第一步采用遍历也就是顺序查找,第二步删除采用正常的覆盖删除。查找这一步不好替代,因为无论是二分查找还是插值查找甚至是斐波那契查找都要求数组元素进行过排序,而哈希查找需要构造额外的空间也不符合要求。因此,我们考虑第二步是否可以优化?
第二步是删除目标元素,一般来说除了覆盖删除,面对数组中删除元素时,在不限制额外空间的情况下还可以使用复制数组的方式进行目标元素删除,原理就是创建一个新数组,对原数组进行遍历把所有非目标元素进行转移,相对于新数组而言,实现了目标元素删除。
上面这个思路其实就是双指针的原型,只不过我们不需要创建新数组也可以完成同样的操作。创造两个指针都指向数组的开始位置,这就相当于我们创建了新旧两个数组,下面的操作其实和复制数组的做法一样,原数组进行遍历就相当于快指针遍历,旧数组进行元素插入就相当于慢指针依次移动。快指针代表的原数组当前元素不是目标元素的话,意味着需要进行复制,实际上由于快慢指针指向同一个元素,复制并且移动到新数组的操作只要将慢指针向后移动就代表完成一次元素复制了;快指针指向的当前元素是目标元素的话,意味着不需要进行复制插入,也就是慢指针所代表的所谓新数组当前的插入元素的位置不需要改变,而快指针所代表的原数组需要继续向后移动直到找到非目标元素在进行复制插入。
动画演示:
代码(Java):
public static int removeElement(int[] nums,int val){
int slowIndex = 0;
for(int fastIndex=0;fastIndex
3、小结
双指针这里需要理解一下,只要我们用两个数组的方式来看待快慢两个指针就可以了。如果你看到这里了,那就给个赞呗,你的鼓励就是我的动力。咱们+_+下一篇+_+见



