剣指offer——11.回転配列の最小値を特定


テーマ:1つの配列の最初のいくつかの要素を配列の末尾に運んで、私たちは配列の回転と呼ばれています.非減算ソート配列の回転を入力し、回転配列の最小要素を出力します.例えば、配列{3,4,5,1,2}は{1,2,3,4,5}の回転であり、この配列の最小値は1である.NOTE:与えられたすべての要素は0より大きく、配列サイズが0の場合は0を返します.
解題の考え方:leetcodeを参照
class Solution:
    def minArray(self, numbers: [int]) -> int:
        i, j = 0, len(numbers) - 1
        while i < j:
            m = (i + j) // 2
            if numbers[m] > numbers[j]: i = m + 1
            elif numbers[m] < numbers[j]: j = m
            else: j -= 1
        return numbers[i]
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return
        if len(rotateArray)==0:
            return 0
        index1=0
        index2=len(rotateArray)-1
        indexMid=index1
        while (rotateArray[index1]>=rotateArray[index2]):
            if (index2-index1)==1:
                indexMid=index2
                break
            indexMid = (index1+index2)//2
            #   index1 index2 indexMid    
            if rotateArray[index1]==rotateArray[index2] and rotateArray[indexMid]==rotateArray[index1]:
                return self.minValue(rotateArray,index1,index2)

            if rotateArray[indexMid]>=rotateArray[index1]:
                index1=indexMid
            if rotateArray[indexMid]<=rotateArray[index2]:
                index2=indexMid

        return rotateArray[indexMid]

    def minValue(self,rotateArray,index1,index2):
        res=rotateArray[index1]
        for i in range(index1+1,index2+1):
            if res>rotateArray[i]:
                res=rotateArray[i]
        return res