代码随想录算法训练营第一天 | 704. 二分查找、27. 移除元素-爱代码爱编程
704.二分查找
二分常用模板,两个
找到符合条件的第一种情况,左闭右开
class Solution {
public:
int search(vector<int>& nums, int target) {
int l=0,r=nums.size()-1;
while(l<r){
int mid=(l+r)/2;
if(nums[mid]>=target) r=mid;
else l=mid+1;
}
if(nums[l]==target) return l;
else return -1;
}
};
找到符合条件的最后一种情况,左开右闭
class Solution {
public:
int search(vector<int>& nums, int target) {
int l=0,r=nums.size()-1;
while(l<r){
int mid=(l+r+1)/2;
if(nums[mid]<=target) l=mid;
else r=mid-1;
}
if(nums[l]==target) return l;
else return -1;
}
};
27.移除元素
暴力思路
1.遍历,遇到nuns[i]为val,再开个循环;
2.内层循环从i位置开始,后面的位置前移一个;
注意
1.别把nums.size()放进循环,提前赋值,手动更改即可;
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int len=nums.size();
for(int i=0;i<len;i++){
if(nums[i]==val){
for(int j=i;j<len-1;j++){
nums[j]=nums[j+1];
}
i--;
len--;
}
}
return len;
}
};
双指针思路
1.i循环遍历快指针,j为慢指针;
2.只要nums[i]不是目标值,就把他赋给慢指针;这样的话到了要删除的元素时,慢指针不动,快指针往下走,就是个覆盖的过程;
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int len=nums.size();
int ans=0;
for(int i=0,j=0;i<len;i++){
if(nums[i]!=val){
nums[j++]=nums[i];
ans++;
}
}
return ans;
}
};