网站次年续费,开发一个游戏需要多少钱,wordpress多媒体mp4,net淘宝网站开发的例子前言
上篇介绍了二分法的相关原理并结合具体题目进行讲解运用#xff0c;本篇将加大难度#xff0c;进一步强化对二分法的掌握。
一. 寻找峰值
1.1 题目链接#xff1a;https://leetcode.cn/problems/find-peak-element/description/
1.2 题目分析:
题目要求返回数组内…
前言
上篇介绍了二分法的相关原理并结合具体题目进行讲解运用本篇将加大难度进一步强化对二分法的掌握。
一. 寻找峰值
1.1 题目链接https://leetcode.cn/problems/find-peak-element/description/
1.2 题目分析:
题目要求返回数组内任一峰值元素的下标时间复杂度要求为log n排除暴力解法直接遍历的可能. 峰值元素大于其左右相邻元素的元素。
1.3 思路讲解
题目给出提示可以假设nums[-1]nums[n]负无穷且要求时间复杂度为log n因此可考虑寻找二段性利用二分法求解。 寻找⼆段性 任取⼀个点 i 与下⼀个点 i 1 会有如下两种情况 • arr[i] arr[i 1] 此时「左侧区域」⼀定会存在⼭峰因为最左侧是负⽆ 穷那么我们可以去左侧去寻找结果 • arr[i] arr[i 1] 此时「右侧区域」⼀定会存在⼭峰因为最右侧是负⽆ 穷那么我们可以去右侧去寻找结果。 当我们找到「⼆段性」的时候就可以尝试⽤「⼆分查找」算法来解决问题。
1.4 代码实现
class Solution {
public:int findPeakElement(vectorint nums) {int left0,rightnums.size()-1;while(leftright){int midleft(right-left1)/2;if(nums[mid]nums[mid-1]){leftmid;}else{rightmid-1;}}return left;}
};二. 寻找旋转排序数组中的最小值
2.1 题目链接https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/
2.2 题目分析
现有一个按照升序排列且元素值各不相同的数组每旋转一次即为把数组原先末尾的值调向第一个将该数组旋转数次后要求返回此时数组内的最小元素时间复杂度为log n
2.3 思路讲解
旋转后的数组满足下图情形其中ABCD均为数组按下标顺序所对应的值且C即为所求。 以D为界限A-B内全都大于DC-D内全都小于D满足二段性因此可考虑使用二分法求解具体步骤如下
令left0rightnums.size()-1,targetnums[right]其中target即为上图中的D求取中点midleft(right-left)/2如果nums[mid]target说明mid此时位于AB区间内需要更新leftmid1如果nums[mid]target说明mid此时位于CD区间内需要更新rightmidwhile循环二分最终nums[left]即为所求。
2.4 代码实现
class Solution {
public:int findMin(vectorint nums) {int left0,rightnums.size()-1;int targetnums[right];//靶区间while(leftright){int midleft(right-left)/2;if(nums[mid]target){leftmid1;}//更新leftelse{rightmid;}//更新right}return nums[left];}
};三. 搜索插入位置
3.1 题目链接https://leetcode.cn/problems/search-insert-position/description/
3.2 题目分析
题中给出一个升序数组和target要求查找target在数组内的位置如果target不存在则返回其应该插入的位置时间复杂度为logn
3.3 思路讲解
时间复杂度为logn且满足二段性因此可考虑使用二分法解决具体步骤如下
令left0rightnums.size()-1,分别作为左右区间求取中点midleft(right-left)/2如果nums[mid]target说明[left,mid]内的所有元素均小于target将left更新为mid1如果nums[mid]target,说明[mid,right]内所有元素均大于等于target将right更新为mid.while循环二分最终leftright此时如果nums[left]target说明数组内所有元素均小于target需要在末尾插入返回left1反之则正常返回left即可
3.4 代码实现
class Solution {
public:int searchInsert(vectorint nums, int target) {int left0,rightnums.size()-1;while(leftright){int midleft(right-left)/2;if(nums[mid]target){leftmid1;}//更新leftelse{rightmid;}//更新right}if(nums[left]target){return left1;}return left;}
};四. 点名
4.1 题目链接https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/
4.2 题目分析
数组内有n个元素代表0-n但其中缺少了0-n中的一个元素返回该值
4.3 思路讲解
该题方法多样可以采取异或法总和累减法等方法解答。由于本篇主题为二分法因此只讲解二分法如何解答该题。 二分法的重点为二段性
观察可知假设缺失元素为target在target左侧[left,target]内每一个元素的值对应其下标在target右侧[target,right]内每一个元素的值都比其下标大1 因此该题二分法具体步骤如下 令left0,rightnums.size()-1作为左右边界 求取中点,midleft(right-left)/2如果nums[mid]mid,则更新leftmid1 如果nums[mid]mid,更新rightmid while循环二分后right即为所求 需注意一种特殊情况当rightnums[right]时说明缺失的数字为n[left,right]内所有元素均有下标一一对应此时需要返回right1 4.4 代码实现
class Solution {
public:int takeAttendance(vectorint records) {int left0,rightrecords.size()-1;while(leftright){int midleft(right-left)/2;if(records[mid]mid){leftmid1;}//更新为leftelse{rightmid;}//更新right}if(records[right]right){return right1;}//缺少的元素为nelse{return right;}}
};小结
关于二分法的介绍就暂告段落啦希望能对大家的学习产生帮助欢迎各位佬前来支持斧正
