把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]
示例 1：
输入：numbers = [3,4,5,1,2]
输出：1
示例 2：
输入：numbers = [2,2,2,0,1]
输出：0
解题思路：可以直接排序找到，但时间复杂度为O(n)，用二分查找可以降为O(logn)。也就是拿中间元素 m 与末尾元素 j 比较，如果m>j，说明最小值在m的右边，否则在左边，如果相等，则分不清在左边还是右边，但此时要么是m的左边的数都相等，要么m的右边的数都相等，或者全部相等。比如120000，此时number[m]=number[j]=0，然后可以用j - - ，然后number[m]=2 > number[j]=0，然后起始元素 i = m+1，(在m的右边)，后面都为0了，自然返回的只能是0。如果是00010，number[m]=
number[j]=0，也可以用 j--，number[m]=0，
number[j]=1，虽然越过了0，但是m的左边都为零，返回的结果还是对的。(当然，也可以在遇到number[m]=number[j]时直接用线性查找，直接从i+1开始查找第一个比i位置的元素的值小的，便是最小值)
算法流程：
1.定义数组的头元素的下标 i=0，末尾元素的下标 j=numbers.size()-1。
2.循环：(i
如果number[m]>number[j]
最小值在m的右边，i=m+1
如果number[m]
如果number[m]=number[j]
j - -
3.返回number[i]
代码：
class Solution {
public:
int minArray(vector
int i=0,j=numbers.size()-1;
while(i
if(numbers[m]>numbers[j])
i=m+1;
else if(numbers[m]
else
j--;
}
return numbers[i];
}
};
推荐阅读
- 算法设计|算法--第四章
- 排序算法|室友1把王者的时间写出了快速排序（）
- 算法|希尔排序——JS实现
- 数据结构|希尔排序——直插排序的更好优化
- LeetCode|Dynamic Programming --- 动态规划刷题(一)
- 算法|2020 必学的10大顶级 Python 开源库
- CMPUT 201解题技巧
- 大数据|超高分辨率显著目标检测，新颖高效的错层嫁接架构PGNet（CVPR2022）
- JAVA|java-单链表反转解法及分析