剣指offer——11.回転配列の最小値を特定
テーマ:1つの配列の最初のいくつかの要素を配列の末尾に運んで、私たちは配列の回転と呼ばれています.非減算ソート配列の回転を入力し、回転配列の最小要素を出力します.例えば、配列{3,4,5,1,2}は{1,2,3,4,5}の回転であり、この配列の最小値は1である.NOTE:与えられたすべての要素は0より大きく、配列サイズが0の場合は0を返します.
解題の考え方:leetcodeを参照
解題の考え方: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