题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
知识点
排序，折半查找
Qiang的思路
对于这道题，如果不管是不是排序，旋转之类的，直接通过遍历就能得到结果，但是显然这样做就没什么意义了。同样也说明，这道题考察的是如何将时间复杂度降低。遍历的时间复杂度为O(n)，因为排好序了，所以可以使用折半查找，时间复杂度为O(logn)。
我们能够发现数组一共有三种情况：
- 长度为0。
- 没有旋转，这算是旋转中的一种特殊情况。
- 正常旋转。
对于第一种情况，只需要返回0即可。对于第二种情况只需要返回第一个值即可，此时第一个元素一定小于最后一个元素。对于第三种情况才是需要使用递归执行的。
既然想使用折半查找的办法去做，那么首先要分析一下中间值的特点。显然，中间值可能有几种情况：
- 大于开头和结尾。也就是说中间值还在旋转之后的前部分。这种情况下最小值一定在后半部。
- 小于开头和结尾。中间值在后部分。此时最小值一定在前半部。
- 等于开头和结尾。这个时候无法确定最小值所在的区域，也就是说折半查找在这种情况下是行不通的。
- 等于开头，不等于结尾。此时结尾一定小于中间值的，所以最小值在后面部分。
-等于结尾，不等于开头。此时开头大于中间值，所以最小值一定在前半部分。
组合一下上面的五种情况：
- 当中间值等于开头和结尾是采用遍历查找。
- 当中间值大于等于开头，在后半部继续查找。（中间值不用考虑）
- 当中间值小于等于结尾，在前半部查找。（中间值需要考虑）
所以能写出如下的代码：
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray)==0:
return 0
while rotateArray[0]>=rotateArray[-1]:
if len(rotateArray)==2:
return min(rotateArray)
mid=int(len(rotateArray)/2)
if rotateArray[0]==rotateArray[-1] and rotateArray[0]==rotateArray[mid]:
return min(rotateArray)
if rotateArray[mid]>=rotateArray[0]:
rotateArray=rotateArray[mid+1:]
elif rotateArray[mid]<=rotateArray[-1]:
rotateArray=rotateArray[:mid+1]
return rotateArray[0]
这个问题中有几点需要注意：
- 当没有旋转或者是检查的串是非递减时（第一项小于最后一项），这种情况需要单独考虑。
- 当第一项，中间一项和最后一项三者相同时，此时是特殊情况，只能通过遍历的方式计算。
作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。
网友评论