题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
时间限制：1秒；空间限制：32768K；本题知识点：查找
解题思路
思路一
首先考虑数组长度为0和1的情况，然后考虑数组元素全部相等的情况，除上述情况外从头到尾遍历数组，只要搜索到后一个元素比前一个小，后一个数即是旋转数组的最小元素。这种做法的时间复杂度为O(n)。python代码：
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray) == 0: #数组长度为0的情况
return 0
elif len(rotateArray) == 1: #数组长度为1的情况
return rotateArray[0]
for i in range(len(rotateArray)-1):
if rotateArray[i]>rotateArray[i+1]:
return rotateArray[i+1]
return rotateArray[0] #数组元素全部相等的情况思路二
再来看这道题目有个特点，旋转之后的数组实际上可以划分成两个有序的子数组，而最小的元素就是两个子数组的分界线。比较好的思路是用二分查找，也可能是面试官考核的出发点。这种做法的时间复杂度为O(logn)。
思路如下：
（1）用两个指针left,right分别指向数组的第一个元素和最后一个元素。
（2）找到数组的中间元素mid。
（3）比较left元素和mid元素的大小，首先考虑元素无重复的情况。
- 如果left元素比mid元素小，则说明mid元素在后一个有序的子数组中，此时最小元素位于mid元素的前面，我们可以让指针right指向中间元素mid；
- 如果left元素比mid元素大，则说明mid元素在前一个有序的子数组中，此时最小元素位于mid元素的后面，我们可以让指针left指向中间元素mid；
- 循环直到左右指针相邻，最终left指针将指向前面数组的最后一个元素，right指针指向后面数组中的第一个元素，而right指针指向的刚好是最小的元素。
（4）考虑元素重复的情况，若出现left,right,mid元素均相等的情况如 {1,0,1,1,1} 则无法进行二分查找，改用顺序查找。
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code
left = 0
right = len(rotateArray)-1
if len(rotateArray)==0:
return 0
while ((right - left) != 1):
mid = (left + right) / 2 #整除
# 中间数和左指针、右指针都相同
if rotateArray[mid] == rotateArray[left] and rotateArray[right]:
return min(rotateArray)
if rotateArray[left] < rotateArray[mid]:
left = mid
else:
right = mid
mid = right
return rotateArray[mid]思路三
最后，分享一个比较bug的做法，能通过但是面试官一定不想给你offer。。。
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code
if rotateArray:
return min(rotateArray)
else:
return 0