伪装成一个老手!
一、二分查找
题目
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
来源:力扣二分查找
阻碍
1. Q1: 为什么想到要用二分法?
A1: 识别关键词:对有序无重复数组进行查找。二分法顾名思义就是从中间分开,通过中间元素与查询的目标值比较不断缩小区间范围,最终定位元素。
2. Q2:查询区间范围如何表达?
A2:一般区间定义常有左闭右闭“[ ]”,左闭右开‘[ )’两种,使用哪一种都可以,但全程区间的定义要保持不变,不能一会是“[ ]”,过一会又是‘[ )’。这是保证代码逻辑正确性的关键。
3. Q3数组中间值mid, 及左left右right的确定?
A3:mid=(left+right)/2, 但一般我们更倾向于使用mid=left+(rigrt-left)/2。尽管在数学运算上mid的计算结果是一样的,但是前者(left+right)的值有可能在计算机中溢出,导致结果错误。
当查询目标值target>num[mid]时,说明target处于右半区间,故需要移动left=mid+1;
当查询目标值target<num[mid]时,说明target处于左半区间,故需要移动right=mid-1 or right=mid-1,我们只需要记住num[mid]已经被判断过了,所以新区间的边界是不应该再包含num[mid]的,所以闭区间“[ ]”right=mid-1,开区间‘[ )’right=mid。
代码
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0;
int right=nums.size()-1;
while(left<=right)
{
int middle=left+(right-left)/2;
if(nums[middle]>target) {right=middle-1;}
else if(nums[middle]<target){left=middle+1;}
else {return middle;}
}
return -1;
}
};
来源:代码随想录
二、移除元素
题目
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
示例:
输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。
来源:力扣移除元素
阻碍
1. Q1:如何删除数组中的元素?
A2:数组存储在一段连续的内存空间,数组中的元素不能被删除,只能被后面的元素覆盖。
2. Q2:数组元素的具体删除操作?
A2:第一步遍历找到目标元素;第二步,目标元素后的元素逐个前移,完成覆盖操作。
3. Q3:什么叫双指针以及两个指针各自的作用?
A3: 双指针就是两个指针(一快一慢),一个指针(快)用来遍历数组寻找目标元素,另一个指针(慢)用来指向更新后数组的当前值。双指针使得原本两层for循环可以减少为一层for循环,降低了时间复杂度。
4. Q4:慢指针如何更新?
A4:满足题目要求是,慢指针停滞(不进行赋值更新),不满足时将快指针赋值慢指针。文章来源:https://www.toymoban.com/news/detail-497939.html
代码
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex=0;
for(int fastIndex=0; fastIndex<nums.size(); fastIndex++){
if(val!=nums[fastIndex]){
nums[slowIndex++]=nums[fastIndex];
}
}
return slowIndex;
}
};
来源:代码随想录文章来源地址https://www.toymoban.com/news/detail-497939.html
到了这里,关于算法-二分查找、移除元素的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!