app网页设计网站,wordpress+百度云图安装,网页游戏排行榜人气,公司信息管理系统文章目录 1.山脉数组的峰顶索引2.寻找峰值3.寻找旋转排序数组中的最小值4.点名希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力#xff01; 本篇接上一篇二分查找#xff0c;主要通过部分题目熟悉二分查找的进阶使用#xff0c;重点强调二段性#xff0c;… 文章目录 1.山脉数组的峰顶索引2.寻找峰值3.寻找旋转排序数组中的最小值4.点名希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力 本篇接上一篇二分查找主要通过部分题目熟悉二分查找的进阶使用重点强调二段性找到两个区间不同的地方在哪多画图划分界限
1.山脉数组的峰顶索引
✏️题目描述 ✏️示例 传送门山脉数组的峰顶索引 题解: 第一步
首先确定二段性把顶峰放到左区间还是右区间取决于你自己会根据取法不同而导致代码不同但是都能求出顶峰索引这里我们放到左区间 第二步
按照我们的划分方式要确保左边区间不会越过分界右边区间同理就要用mid和mid-1这种划分方式。如果在左区间那么mid会有等于峰顶索引即left mid如果在右区间mid及其后面的值都不可能是峰顶索引即right mid - 1 细节问题: 对于二分查找进阶模版如果在if语句的函数体里有减法操作时那么计算mid的公式就要1 代码实现:
#include iostream
#include vector
using namespace std;class Solution
{
public:int peakIndexInMountainArray(vectorint arr) {int left 0, right arr.size() - 1;while (left right){int mid left (right - left 1) / 2;if (arr[mid] arr[mid - 1]){left mid;}else{right mid - 1;}}return right;}
};2.寻找峰值
✏️题目描述 ✏️示例 传送门寻找峰值 题解: 第一步
首先确定二段性可以分为在上坡或者下坡其实这道题和山脉数组的峰顶索引是一样的这里我们顶峰放在右区间里 第二步
按照我们的划分方式要确保右边区间不会越过分界左边区间同理就要用mid和mid1这种划分方式。如果在右区间那么mid会有等于峰顶索引即right mid如果在左区间mid及其前面的值都不可能是峰顶索引即left mid 1 代码实现:
#include iostream
#include vector
using namespace std;class Solution
{
public:int findPeakElement(vectorint nums) {int left 0, right nums.size() - 1;while (left right){int mid left (right - left) / 2;if (nums[mid] nums[mid 1]){left mid 1;}else{right mid;}}return left;}
};3.寻找旋转排序数组中的最小值
✏️题目描述 ✏️示例 传送门寻找旋转排序数组中的最小值 题解: 第一步
根据画图似乎不太好确认二段性但我们可以发现以D点为分界点左区间的数A到B都大于D右区间的数C到D都小于D那么由此就能确定二段性不断向中寻找最小的数 第二步
如果在右区间那么mid会有等于最小值即right mid如果在左区间mid及其前面的值都不可能是最小值即left mid 1 代码实现:
#include iostream
#include vector
using namespace std;class Solution
{
public:int findMin(vectorint nums) {int left 0, right nums.size() - 1;int x nums[right];while (left right){int mid left (right - left) / 2;if (nums[mid] x){left mid 1;}else{right mid;}}return nums[right];}
};4.点名
✏️题目描述 ✏️示例 传送门点名 题解: 第一步
在连续数组的前提下缺失数字的位置开始下标与实际值不同很明显二段性立马就出来了 第二步
如果在右区间那么mid会有等于缺失值的实际位置索引即right mid如果在左区间mid及其前面的值都不可能是缺失值的实际位置索引即left mid 1 代码实现:
#include iostream
#include vector
using namespace std;class Solution
{
public:int takeAttendance(vectorint records) {int left 0, right records.size() - 1;while (left right){int mid left (right - left) / 2;if (records[mid] mid){left mid 1;}else{right mid;}}return records[left] left ? left 1 : left;}
};希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力
