LeetCode153 Find Minimum in Rotated Sorted Array

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

样例

1
2
3
4
Input:
[4, 5, 6, 7, 0, 1, 2]
Output:
0

思路

递增的原始数组(没有重复的元素),经过某个中枢元素旋转后,得到一个新的数组。现在只给出新数组,求其中最小的元素。

直接遍历新数组,就可以找到最小的元素,复杂度$\mathcal{O}(n)$,但这显然不是我们想要的。

由于原始数组单调,不妨考虑二分,但是怎么更新$l$和$r$呢?

如果此时位于$mid$的元素大于位于$r$的元素,那么说明$mid$正位于中枢元素的左侧(中枢元素就是0),即$[l, mid]$这一段区间都不可能是答案,于是更新l = mid + 1

反之,说明$mid$位于中枢元素的右侧(或者就是中枢元素本身),于是更新r = mid

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[m] > nums[r]) l = m + 1;
else r = m;
}
return nums[l];
}
};
分享到 评论