令人惊讶的是,这一题竟然答题答过,但我没有丝毫印象,啊,该死啊。
思路1:
这种删除元素的题目,我们一般都是采用双指针。由于题目要求删除数组中等于val的元素,那么输出元素的长度一定小于原来数组的长度。可以使用双指针:右指针指向要处理的元素,左指针指向下一个将要赋值的位置。
如果右指针指向的元素不等于val,那么它是输出数组的第一个元素,我们就将右指针指向的位置复制到左指针,同时左右指针同时加加。
如果右指针指向的元素等于val,这个元素不能在输出数组里面,此时右指针向前走一位,而左指针不动。
int removeElement(int* nums, int numsSize, int val) { int left=0; for(int right=0;right<numsSize;right++) { if(nums[right]!=val) { nums[left]=nums[right]; left++; } } return left; }
思路2:
如果要移除的元素在数组的开头,那么我们需要把所有元素都左移一位。同时我们也注意到数组的顺序可以改变,那么,我们可以直接把最后一个元素移到头的位置上,同样满足要求。我们此时使用双指针,分别位于数组的头和尾,向中间移动遍历该序列。
当左指针指向的元素等于val,此时将右指针指向的元素赋值给左指针所指向的位置。然后右指针左移一位,如果赋值过来的值也恰好等于val,可以把右指针指向的值继续赋值过来,(左指针指向val的值会继续被覆盖),知道左指针指向的值不等于val。当左右指针重合,遍历结束。这两个指针总共最多遍历了1次。
int removeElement(int* nums, int numsSize, int val) { int left=0,right=numsSize-1; while(left<=right) { if(nums[left]==val)//如果左边的值等于要寻找到数值 { nums[left]=nums[right]; right--; } else { left++; } } return left; }