模板设计器,专注番禺网站优化,常州网上挂号预约平台,舆情运营岗位主要做什么1. 题目解析
Leetcode链接#xff1a;153. 寻找旋转排序数组中的最小值 这个题目乍一看很长很复杂#xff0c;又是旋转数组又是最小值的
但是仔细想想#xff0c;结合题目给的示例#xff0c;不难看出可以用二分的方法来解决
核心在于找到给定数组里面的最小值 2. 算法原…1. 题目解析
Leetcode链接153. 寻找旋转排序数组中的最小值 这个题目乍一看很长很复杂又是旋转数组又是最小值的
但是仔细想想结合题目给的示例不难看出可以用二分的方法来解决
核心在于找到给定数组里面的最小值 2. 算法原理
题目规定的数组规则如下图所示 我们的目标是找到一个特定的点C。
从给定的图像中我们观察到在区间[AB]内的所有点的值都严格大于D点的值而C点的值则严格小于D点的值。但需要注意的是当区间[CD]只包含一个元素时C点的值有可能等于D点的值。
因此我们初始化两个指针left和right分别代表搜索区间的左右边界。接着根据中间点mid的值与D点值的比较结果我们可以确定下一次搜索的区间
如果mid位于[AB]区间内即mid的值严格大于D点的值那么下一次搜索区间将缩小为[mid 1right]。如果mid位于[CD]区间内即mid的值小于或等于D点的值那么下一次搜索区间将缩小为[leftmid]。
当搜索区间的长度缩减为1时我们就找到了所需的点C。 3. 代码编写
class Solution {
public:int findMin(vectorint nums) {int n nums.size() - 1;int left 0, right n, mid 0;while(left right){mid (left right)/2;if(nums[mid] nums[n]){left mid 1;}else if(nums[mid] nums[n]){right mid;}}return nums[left];}
};
The Last
嗯就是这样啦文章到这里就结束啦真心感谢你花时间来读。
觉得有点收获的话不妨给我点个赞吧
如果发现文章有啥漏洞或错误的地方欢迎私信我或者在评论里提醒一声~
