0%

机试——旋转数组

发表于 更新于 阅读次数： Valine：
本文字数： 72 阅读时长 ≈ 1 分钟

旋转数组的最小数字

​ 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 

1
例如:数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        
        if len(rotateArray) == 0:
            return 0
        left = 0
        right = len(rotateArray) - 1


        def find_rotate_index(arr, left, right):
            if right-left <= 1:
                return right
            mid = (left + right) >> 1

            # 当左半边有序
            if arr[left] <= arr[mid]:
                return find_rotate_index(arr,mid,right)
            else:
                return find_rotate_index(arr,left,mid)


        min_index = find_rotate_index(rotateArray, left, right)
        return rotateArray[min_index]