徐州建设网站,做网站用lunx,山西网站开发二次开发,搜索郑州网站面试经典 150 题 ---- 移除元素 移除元素方法一#xff1a;双指针方法二#xff1a;双指针优化 移除元素
方法一#xff1a;双指针
题目要求在原数组的基础进行元素的删除#xff0c;所以输出的数组长度一定小于原数组的长度#xff0c;因此可以使用双指针#xff0c;r… 面试经典 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) 仅需要常数的空间保存若干变量
