黑龙江建设网网站,wordpress 菜单 主页,优秀网站,怎样自己创造网站这一篇分享一道在数组中寻找峰值的题目#xff0c;使用到分而治之#xff0c;二分查找等思想。本文章会讲解这个二分查找的本质#xff0c;以及为什么要用二分查找#xff0c;它能解决哪一类题目#xff1f;目录#xff1a;一.题目及其要求1.分而治之2.题目思路3.具体做法…这一篇分享一道在数组中寻找峰值的题目使用到分而治之二分查找等思想。本文章会讲解这个二分查找的本质以及为什么要用二分查找它能解决哪一类题目目录一.题目及其要求1.分而治之2.题目思路3.具体做法配图演示4.复杂度分析二.剖析二分查找1.本质2.优点3.适用场景一.题目及其要求1.给定一个长度为n的数组返回其中任何一个峰值的索引2.峰值元素是指其值严格大于左右相邻值的元素3.数组两个边界可以看成是最小nums[−1]nums[n]−∞4.峰值不存在平的情况即相邻元素不会相等5.峰值从第二个数开始不考虑边界的-∞如输入[2,4,1,2,7,8,4]时会形成两个山峰一个是索引为1峰值为4的山峰另一个是索引为5峰值为8的山峰如下图所示示例输入[2,4,1,2,7,8,4]返回值1 说明4和8都是峰值元素返回4的索引1或者8的索引5都可以输入[1,2,3,1]返回值2 说明3 是峰值元素返回其索引 21.分而治之分治即“分而治之”意思就是把一个复杂大问题分成若干个简单的小问题当小问题解决后大问题也就迎刃而解。“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题子题继续按照这样划分直到问题可以被轻易解决“治”指的是将子问题单独进行处理。经过分治后的子问题将若干个子问题进行合并才能得到原问题的解因此整个分治过程经常用递归来实现。2.题目思路因为题目只需要找到其中一个波峰因此不断地往高处走一定会有波峰。那我们可以每次找一个标杆元素将数组分成两个区间每次就较高的一边走因此也可以用分治来解决而标杆元素可以选择区间中点。//右边是往下不一定有坡峰
if(nums[mid] nums[mid 1])right mid;
//右边是往上一定能找到波峰
elseleft mid 1;下面配图进行理解上面代码3.具体做法配图演示1二分查找首先从数组首尾开始每次取中间值直到首尾相遇。2如果中间值的元素大于它右边的元素说明往右是向下我们不一定会遇到波峰但是那就往左收缩区间。3如果中间值大于右边的元素说明此时往右是向上向上一定能有波峰那我们往右收缩区间。4最后区间收尾相遇的点一定就是波峰。下面是配图演示4.代码实现class Solution {
public:int findPeakElement(vectorint nums) {int left 0;int right nums.size() - 1;//二分法while(left right){ int mid (left right) / 2;//右边是往下不一定有坡峰if(nums[mid] nums[mid 1])right mid;//右边是往上一定能找到波峰elseleft mid 1;}//其中一个波峰return right; }
};
4.复杂度分析时间复杂度O(log2n)二分法最坏情况对整个数组连续二分最多能分log2n次。空间复杂度O(1)常数级变量无额外辅助空间。二.剖析二分查找1.本质 二分查找的本质是二段性二分查找的过程本质是对可行区间的压缩。只要满足二段性的问题都可以用二分查找解决。2.优点通过对有序数组进行逐步缩小范围的操作将查找时间从线性时间降低到了对数时间因此它是一种非常高效的搜索算法。3.适用场景二分查找的时间复杂度为O(log n)比其他搜索算法的复杂度要低得多因此它被广泛应用于各种搜索场景中。 在这里二段性的体现是峰值的左边单调增右边单调减。你可能会反驳给我们的数值不只有一个峰值但是只要我们控制好条件一定可以把范围压缩到只有一个峰值的情况来看看该怎么处理nums[mid] nums[mid 1]说明在“上坡”则可以使left mid 1因为mid肯定不是峰值向“峰”处压缩nums[mid] nums[mid 1]说明在“下坡”则应该使right midmid可能是峰值往“峰”处压缩虽然开始left和right之间可能有多个峰值但是随着left和right不断逼近最后两者之间一定会压缩到一个峰值上因为两者都是向“峰”不断靠近的但是不会超过最终的“峰”。望上文对你有帮助谢谢你的阅览后面会持续分享算法题目大家可以关注一下。 2023.02.18 From努力进大厂的新青年
