移除元素
思路
- 题目没有规定时间复杂度，那么我们最容易想到的方法肯定是利用两层for循环来解决问题
- 即遍历数组，如果数组元素等于val，那就将这个元素后面的元素往前移，将这个值为val的元素覆盖
- 这样的暴力解法的时间复杂度为O(n2)
- 那这题可不可以缩短时间，使时间复杂度为O(n)呢？当然可以，这里我们就需要用到双指针中的快慢指针思想
- 定义快指针fast，用来遍历整个数组，慢指针slow用来确定新数组（即删除值为val元素后·数组）的下标，并都初始化为0
- 当nums[fast]不为val时，那就使nums[slow]的值为nums[fast]，同时slow++，相当于保留数组元素
- 当nums[fast]等于val时，那就使fast继续遍历，而slow不变，相当于删除了值为val的元素
实现代码
方法一
int removeElement(int* nums, int numsSize, int val){ int i,j; for(i=0;i<numsSize;i++) { if(nums[i] == val) { for(j=i+1;j<numsSize;j++) nums[j-1] = nums[j]; numsSize--; //数组大小减一 i--; //由于后面的元素往前覆盖了一个位置，因此i要向前走一个 } } return numsSize; }
方法二（快慢指针）
int removeElement(int* nums, int numsSize, int val){ int fast,slow = 0; for(fast = 0; fast < numsSize; fast++) { if(nums[fast] != val) nums[slow++] = nums[fast]; } return slow; }
ps:快慢指针的动态图来自《代码随想录》——https://programmercarl.com/
