题目
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。
示例 1:
1
2 输入:[3,4,5,1,2]
输出:1示例 2:
1
2 输入:[2,2,2,0,1]
输出:0来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
从简单例子入手
1 | [2,3,4,1] |
我们的思路为二分查找,无重复数字的情况很简单(注意一种特殊情况是不旋转)。而有重复数字的情况复杂一些。
由于我们的策略是判断中间位置的元素与数组第一个元素(大于等于最小元素的最小元素)的大小:
- 如果大于,证明最小元素不在左半区间(左半区间非严格递增);
- 如果小于,证明中点取得位置被旋转了,也就是说最小元素在左半区间(含中点);
- 如果等于,我们无法判断中点所处位置,这时我们可以将中点与右侧区间的最大值(最右侧元素)比较,如果大于,那么可以判定中点在第一个非严格递增区间,而最小值在右侧区间;如果小于,整个区间为非严格递增,这种情况属于没有旋转;如果等于,我们无法判断位置,只能遍历。
代码
1 | class Solution { |
- 时间复杂度$O(N)$,因为存在必须遍历的情况
- 空间复杂度$O(1)$