python官方题解

此题大家如有想到的方法就是直接进行顺序的查找,复杂度为O(n).
但是我们看到题中是给出的有序的旋转数组,我们可以采用二分法来进行求解,其复杂度为O(logn).
这里我们需要利用带有条件的二分法来进行求解:

第一步我们可以将这个旋转的数组看作是前后两个有序的子数组,然后设定我们的中间值 mid = (start + end) // 2.

第二步我们能够看到,当我们选取的中间值 mid 所对应的值大于 start 所对应的值时,说明此时 mid 还在第一有序的数组中,而我们所要求解的最小值是在第二个有序数组的第一个位置,此时也就是在 mid 的后面,我们就将 start 移到 mid 所在的位置.

第三步,当我们的 end 所对应的值大于 mid 所对应的值时,说明最小值可能是 mid 所对应的值或者在 mid 的前面,我们将 end 移到 mid 所在的位置.

第四步,最后我们的 end 所在的位置就是最小值的位置,直接返回即可.

我说下,在牛客的这道题目中,以上的方法就可以提交完成,但是当我们看剑指offer的书时,有这样的特例 比如数组 10111 , 这是会出现当 start mid end 所对应位置的值相等,这时候我们的程序就不能找到最小值,当出现这样的情况是 我们采用将 start 和 end 区间里面的值进行顺序查找来找出最小值.
我下面的代码是完整的代码,考虑了所有的情况,如有问题希望您指正,谢谢!!!!!

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        if len(rotateArray) == 1:
            return rotateArray[0]
        start = 0
        end = len(rotateArray)-1

        while rotateArray[start] >= rotateArray[end]:
            if end - start == 1:
                break
            mid = (start + end) // 2
            if rotateArray[start] == rotateArray[mid] and rotateArray[end] == rotateArray[mid]:
                #进行顺序查找
                temp = rotateArray[start]
                for i in range(start,end + 1):
                    if temp < rotateArray[i]:
                        temp = rotateArray[i]
                return temp
            if rotateArray[mid] >= rotateArray[start]:
                start = mid
            elif rotateArray[end] >= rotateArray[mid]:
                end = mid
        return rotateArray[end]