wap网站做微信小程序,苏州网站建设自助建站收费,做某个网站接口违法,网页设计培训机构哪家好本专栏内容为#xff1a;代码随想录训练营学习专栏#xff0c;用于记录训练营的学习经验分享与总结。 文档讲解#xff1a;代码随想录 视频讲解#xff1a;二分查找与移除元素 #x1f493;博主csdn个人主页#xff1a;小小unicorn ⏩专栏分类#xff1a;C #x1f69a… 本专栏内容为代码随想录训练营学习专栏用于记录训练营的学习经验分享与总结。 文档讲解代码随想录 视频讲解二分查找与移除元素 博主csdn个人主页小小unicorn ⏩专栏分类C 代码仓库小小unicorn的代码仓库 关注我带你学习编程知识 Day1 二分查找题目分析解题思路写法一写法二 移除元素题目分析思路暴力双指针法 总结 二分查找
题目分析
题目描述给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。
题目来源704.二分查找
解题思路
这道题目的前提是数组为有序数组同时题目还强调数组中无重复元素因为一旦有重复元素使用二分查找法返回的元素下标可能不是唯一的这些都是使用二分法的前提条件当大家看到题目描述满足如上条件的时候可要想一想是不是可以用二分法了。
二分查找涉及的很多的边界条件逻辑比较简单但就是写不好。例如到底是 while(left right) 还是 while(left right)到底是right middle呢还是要right middle - 1呢
大家写二分法经常写乱主要是因为对区间的定义没有想清楚区间的定义就是不变量。要在二分查找的过程中保持不变量就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作这就是循环不变量规则。
写二分法区间的定义一般为两种左闭右闭即[left, right]或者左闭右开即[left, right)。
写法一
第一种写法我们定义 target 是在一个在左闭右闭的区间里也就是[left, right] 。
在这个区间内要有以下两点
1.while (left right) 要使用 。 这是因为left right是有意义的所以使用 。
2.if (nums[middle] target) 那么 right 要赋值为 middle - 1。 这是因为当前这个nums[middle]一定不是target那么接下来要查找的左区间结束下标位置就是 middle - 1 例如在数组1,2,3,4,7,9,10中查找元素2如图所示
代码解决
class Solution
{
public:int search(vectorint nums, int target) {//定义左闭右闭区间int left0;int rightnums.size()-1;while(leftright){int middleleft((right-left)/2);//说明target在左区间if(nums[middle]target)rightmiddle-1;//target在右区间else if(nums[middle]target)leftmiddle1;else//找到了return middle;}//未找到目标值return -1;}
};时间复杂度O(log n) 空间复杂度O(1)
写法二
如果说定义 target 是在一个在左闭右开的区间里也就是[left, right) 那么二分法的边界处理方式则截然不同。
有如下两点
1.while (left right) 这里使用 这是因为left right在区间[left, right)是没有意义的
2.if (nums[middle] target) right 更新为 middle 这是因为当前nums[middle]不等于target去左区间继续寻找而寻找区间是左闭右开区间所以right更新为middle即下一个查询区间不会去比较nums[middle] 在数组1,2,3,4,7,9,10中查找元素2如图所示注意和方法一的区别 代码解决
class Solution {
public:int search(vectorint nums, int target) {int left 0;int right nums.size(); // 定义target在左闭右开的区间里即[left, right)while (left right) { // 因为left right的时候在[left, right)是无效的空间所以使用 int middle left ((right - left) 1);if (nums[middle] target) {right middle; // target 在左区间在[left, middle)中} else if (nums[middle] target) {left middle 1; // target 在右区间在[middle 1, right)中} else { // nums[middle] targetreturn middle; // 数组中找到目标值直接返回下标}}// 未找到目标值return -1;}
};移除元素
题目分析
题目描述给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。 不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 题目来源27.移除元素
思路
暴力
两层for循环一个for循环遍历数组元素 第二个for循环更新数组。
// 时间复杂度O(n^2)
// 空间复杂度O(1)
class Solution {
public:int removeElement(vectorint nums, int val) {int size nums.size();for (int i 0; i size; i) {if (nums[i] val) { // 发现需要移除的元素就将数组集体向前移动一位for (int j i 1; j size; j) {nums[j - 1] nums[j];}i--; // 因为下标i以后的数值都向前移动了一位所以i也向前移动一位size--; // 此时数组的大小-1}}return size;}
};时间复杂度O(n^2) 空间复杂度O(1)
双指针法
双指针法快慢指针法 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。 定义快慢指针
快指针寻找新数组的元素 新数组就是不含有目标元素的数组 慢指针指向更新 新数组下标的位置
代码解决
class Solution
{
public:int removeElement(vectorint nums, int val) {int slowIndex0;for(int fastIndex0;fastIndexnums.size();fastIndex){//只要不等于val就往后移动if(val!nums[fastIndex])nums[slowIndex]nums[fastIndex];}return slowIndex;}
};时间复杂度O(n) 空间复杂度O(1)
总结
在今天我们通过两道典型例题知道了什么是二分法用到了双指针算法思想希望通过这两道例题能对双指针和二分法有更深层的理解。
