面试经典 150 题 ---- 移除元素
面试经典 150 题 ---- 移除元素
- 移除元素
- 方法一：双指针
- 方法二：双指针优化
移除元素
方法一：双指针
题目要求在原数组的基础进行元素的删除，所以输出的数组长度一定小于原数组的长度，因此可以使用双指针，rigth 指针指向将要处理的元素，left 指针指向将要赋值的元素的位置。
- 如果
right指针指向的元素不等于val，那么它就一定是将要输出的元素，将该元素赋值到left指针指向的位置，同时将right和left指针同时右移。 - 如果
right指针指向的元素等于val，那么它就一定不是要输出的元素，此时left不动，right右移。
最后 left 的值就是要输出的数组的长度。
class Solution {public int removeElement(int[] nums, int val) {int n = nums.length;int left = 0;for (int right = 0; right < n; right++) {if (nums[right] != val) {nums[left] = nums[right];left++;}}return left;}
}
时间复杂度： O(n)
n 为数组的长度，最多只需要遍历该数组两遍
空间复杂度： O(1)
仅需要常数的空间保存若干变量
方法二：双指针优化
方法一中，我们的两个指针都是从 0 开始的，实际上，我们可以一个指针从头开始，一个指针从尾开始，这样就最多仅需要遍历一次数组就可以了。
class Solution {public int removeElement(int[] nums, int val) {int left = 0;int right = nums.length;while (left < right) {if (nums[left] == val) {nums[left] = nums[right - 1];right -- ;} else {left ++ ;}}return left;}
}
时间复杂度： O(n)
n 为数组的长度，最多只需要遍历该数组一遍
空间复杂度： O(1)
仅需要常数的空间保存若干变量