删除数组中的指定数字我们要做到:
1.找到数组中存在的指定数字
2.删除它,并保持其他数字的相对位置不变,可以正常输出。
于是我们的任务就是**找到指定数字以及保证除此以外的数字可以按原来的相对位置输出。**这样单在效果上看我们就完成了删除指定元素的效果。
总而言之,如果,我们能保证除指定元素以外的数字能正常输出那么在视觉效果上我们就达到了删除指定元素的效果。
综上,如果不使用双指针,其实有一种更简单的方法:设指定元素为val,我们先建一个数组ans,遍历题中给的数组nums,如果nums[i] ! =val,那么我们将nums[i],存储在ans中,最后,输出ans.我们就得到了一个指定元素被删除的nums.
如果使用双指针: 双指针的删除采用的是覆盖的方法。 设指定的数字为val, 一个指针left负责检测数字,当检测到val时,另一个指针right的任务就是帮第一个指针找到替代该位置val 的数字。当right遍历到数组尾的时候就结束循环用val之后的第一个非val来替代val,这就是覆盖 。
现在我们以及弄清了双指针删除的原理,但是如果我们只是这样做会出现一个问题:现在假设题中给的数组为【1,2,2,3,4,5】,要删除的元素是2,
两个2的位置会分别被3,4,替代,我们的输出结果是【1,3,4,3】,观察发现我们还需要原来3的位置被5替代,才能达到我们想要的效果。那怎样才能让3的位置也能启动覆盖机制呢?
我想到的办法是:如果这个数字a用来去替代前面val的位置了,那么就将a位置的数值赋为val,这样当left指针遍历到时,就可以启动循环机制,不会造成数字的重复输出。 如上例,俩个2被3,4,替代,此时3,4,的位置为2,当遍历到原来3的位置时,会启动覆盖机制,原来3 的位置会被5覆盖。就可以输出【1,3,4,5】啦!!!开心~
class Solution16 {
public int removeElement(int[] nums, int val) {
if (nums == null || nums.length == 0) return 0;
int p = 0;
int q = 1;
while(q<nums.length){
if(nums[p]!=val){//当数字不为val 时,两指针都向前移动
p++;
q++;
}else{//覆盖机制启动
while(nums[q]==val){ //right指针开始寻找
q++;
}
if(nums[q]!=val){//left指针找到啦
nums[p]=nums[q];//nums[right]=nums[left]
nums[q]=val;//nums[left]=val
q++;
p++;
}
}
}
return p;
}
}