题目
153. 寻找旋转排序数组中的最小值
已知一个长度为 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.length
- 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- nums 中的所有整数 互不相同
- nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
我的代码（TypeScript）
function findMin(nums: number[]): number {
let s = 0;
let e = nums.length - 1;
let result = nums[0];
while (s < e) {
if (s == e - 1) {
result = Math.min(result, nums[s], nums[e]);
break;
}
let m = Math.floor((s + e) / 2);
result = Math.min(result, nums[s], nums[m], nums[e]);
if (nums[s] < nums[m]) {
if (nums[m] < nums[e]) {
break;
} else {
s = m;
}
} else {
if (nums[m] < nums[e]) {
e = m;
} else {
break;
}
}
}
return result;
};点评
基本上和33. 搜索旋转排序数组一样，
我的解法
二分查找，找最小值，下一步取左还是右再进一步判断。
或者也可以有另一个思路，找从头开始递增的最后一个数，然后这个数的下一个数就是最小值。
应该也是O(logn)的复杂度。
官方代码更简洁，效果类似。我懒得想如何再优化了，就这样吧……
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog