153. 寻找旋转排序数组中的最小值
一句话套路与右端点比较收缩,答案落在 lo
题目描述
已知一个长度为
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) 的算法解决此问题。
示例 1:
输入:nums = [3,4,5,1,2] 输出:1 解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。
示例 2:
输入:nums = [4,5,6,7,0,1,2] 输出:0 解释:原数组为 [0,1,2,4,5,6,7] ,旋转 4 次得到输入数组。
示例 3:
输入:nums = [11,13,15,17] 输出:11 解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。
提示:
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组,并进行了1至n次旋转
思路
时间
O(log n)空间
O(1)思路
和「右端点」比。nums[mid] > nums[hi] 说明最小值一定在 mid 右边 -> lo = mid+1;
否则最小值在 [lo, mid] 里 -> hi = mid(mid 仍可能是答案,不能 -1)。
为什么和右端点比而不是左端点?和左端点比无法区分「未旋转」与「已旋转」。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0153 {
class Solution {
public:
int findMin(vector<int>& nums) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi])
lo = mid + 1;
else
hi = mid;
}
return nums[lo];
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0153::Solution s;
vector<int> a{3, 4, 5, 1, 2};
CHECK_EQ(s.findMin(a), 1);
vector<int> b{4, 5, 6, 7, 0, 1, 2};
CHECK_EQ(s.findMin(b), 0);
vector<int> c{11, 13, 15, 17}; // 未旋转
CHECK_EQ(s.findMin(c), 11);
vector<int> d{2, 1};
CHECK_EQ(s.findMin(d), 1);
vector<int> e{1};
CHECK_EQ(s.findMin(e), 1);