代码随想录刷题营day1|双指针
双指针思想
- 双指针思想主要应用场景是解决双重循环问题,降低算法的时间复杂度
- 一般有两个指针完成数组的遍历,双指针可能都从数组首元素出发,也有可能一个指针从前向后遍历、另一个指针从后向前遍历
- 使用快慢指针要特别注意边界条件的处理,即什么时候停下来
Leetcode27.移除元素
题目分析
- 不能使用额外的空间,就要求我们只能在原数组中做改动
- 需要移除等于
val
的元素,想到的就是遍历该数组,如果遇到等于val
的元素,那就与后面不等于val
元素做swap,并记录最后一个不等于val
元素的索引,这样也就间接知道了移除后数组的新长度
思路
-
采用双指针的思想,左指针从前向后遍历整个数组,如果遍历到的元素不等于
val
,继续向后遍历;否则,右指针从后向前遍历,找到第一个不等于val
的元素,两元素交换,同时更新左指针,右指针 -
边界条件:什么时候停止?右指针标志从后向前第一个不等于val元素的位置,所以循环遍历结束的条件应该是
i > j
,这样while循环条件就是i <= j
代码实现
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
if (nums.size() == 0)
return 0;
int i = 0;
int j = nums.size() -1;
while(i <= j){
if(nums[i] == val){
nums[i] = nums[j];
j--;
}
else{
i++;
}
}
return i;
}
};