题解 | #旋转数组的最小数字#
旋转数组的最小数字
https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba
class Solution:
def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
# write code here
if len(rotateArray) == 1:
return rotateArray[0]
left, right = 0, len(rotateArray)-1
while left < right:
mid = (left + right) // 2
if rotateArray[mid] > rotateArray[right]:
left = mid + 1
elif rotateArray[mid] < rotateArray[right]:
right = mid
else:
right = right - 1
return rotateArray[left]
解题思路：
python中有min函数和列表排序方法可求得最小值，但是这两种方法的时间复杂度为O(n)，舍弃不用。
该题用二分法来解决较为合适：
1、特殊情况：列表长度为1，则最小值为列表中仅存在的那个值；
2、因为列表为非降序列表且旋转，所以若中间值大于最末尾的值，则最小值在右半区间；反之若中间值小于最末尾的值，则最小值在左半区间；若中间值等于最末尾的值，表示该列表中存在重复值，我们只需将最左边的索引往前移动一个重新检查即可。
#python##算法##旋转数组的最小数字#python 算法 文章被收录于专栏
python算法
