题目描述
- 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为
数组的旋转
。
- 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。
- 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
- 给出的所有元素都大于0,若数组大小为0,请返回0。
理解
- 非减排序想说明什么
这说明说明旋转前的数组是按照非减的顺序排列的
- 引入数组的旋转是为了什么
这说明旋转后的数组分成了两个非减排序的数组,记为array1和array2,array1中的任意元素是大于等于array2中所有数的,所以array2中的第一个数就是我们要找的旋转数组中最小的数。
- 旋转数组的最小数字
解题思路
思路1
无非是要找出给定数组中的最小元素,不考虑什么数组旋转,直接简单粗暴解决
class Solution:
def minNumberInRotateArray(self, rotateArray):
min = rotateArray[0]
if len(rotateArray) > 0:
for i in range(1,len(rotateArray)):
if rotateArray[i] < min:
min = rotateArray[i]
return min
else:
return 0
或者
class Solution:
def minNumberInRotateArray(self, rotateArray):
if len(rotateArray) == 0:
return 0
else:
return min(rotateArray)
思路2
利用二分查找法
- 设置中间点,标记旋转数组首元素和尾元素,中间点将数组分成两半。
- 如果中间点大于等于首元素,说明最小数字在数组后一半,如果中间点小于等于尾元素,说明最小数字在数组前一半。依次改变首尾元素的位置,当尾元素和首元素挨着的时候,这时候尾元素就是所找的最小值。有一点特殊的是,当首元素等于尾元素等于中间值时,只能对数组进行顺序查找。
class Solution:
def minNumberInRotateArray(self, rotateArray):
array_len = len(rotateArray)
left = 0
right = array_len - 1
if array_len==0:
return 0
else:
while (right - left)> 1:
mid = (left + right)//2
if rotateArray[mid] == rotateArray[left] and rotateArray[mid] == rotateArray[right]:
min = rotateArray[left]
for i in range(left,right):
if rotateArray[i] < min:
min = rotateArray[i]
return min
elif rotateArray[mid]>=rotateArray[left]:
left = mid
elif rotateArray[mid]<=rotateArray[right]:
right = mid
return rotateArray[right]