题目描述
已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:
若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]
注意,数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
样例
输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。
输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 3 次得到输入数组。
输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。
算法1
该题目存在三种情况:
- 是一个上升序列,则直接返回下标为0的元素
- 是一个下降序列,则直接返回下标为nums.size()-1的元素
- 是一个由两个上升序列组成的序列,中间断开的点即为拐点,该拐点即为最小值的索引。即 nums[nMid]<nums[nMid-1] && nums[nMid]<nums[nMid+1]。
同时最小值也可能出现在下标为0处,因此需要对拐点和小标为0进行比较,返回最小值即可。
拐点情况:观察这两个上升序列,可知,左边任意一点都大于末尾端点,右边任意一点都小于末尾端点,因此末尾端点可以作为二分查找的条件。(可以参考二分经典场景之“左边上升,右边下降,查找该中间点”,该场景也可以使用起始端点和末尾端点作为比较条件)
1. 左边序列:当nMid在左边序列,即nums[nMid]>nums[nEnd],则答案应在右边,更新nLeft=nMid+1。
2. 右边序列:当nMid在右边序列,即nums[nMid]<nums[nEnd],即答案应在左边,更新nRight=nMid-1。
时间复杂度
logn
C++ 代码
class Solution {
public:
int binarySearch(vector<int>& nums)
{
int nEnd=nums.size()-1;
int nLeft=0,nRight=nums.size()-1;
while(nLeft<=nRight)
{
// 特判一下该种情况,以防下面求取nMi的这种写法漏判nRight==1进入nMid==0则直接返回这种情况
if(nLeft==nRight-1) return nums[nLeft]<nums[nRight]?nLeft:nRight;
int nMid=nLeft+((nRight-nLeft)>>1);
if(nMid==0||nMid==nums.size()-1) return nMid;// 走到边界直接返回,以防数组下标越界
if(nums[nMid]<nums[nMid-1]&&nums[nMid]<nums[nMid+1])
{
return nMid;// 拐点情况
}
else if(nums[nMid]<nums[nEnd])
{
nRight=nMid-1;// 处于较小数值的部分,则说明答案应在左边
}
else
{
nLeft=nMid+1;// 处于较大数值的部分,说明答案应在右边
}
}
return 0;
}
int findMin(vector<int>& nums) {
// 计算拐点的下标
int nMid=binarySearch(nums);
// 最小值只可能出现在下标为0的点和拐点,取二者最小值即可
return nums[nMid]<nums[0]?nums[nMid]:nums[0];
}
};