問題
本日はFind the Rotation Count in Rotated Sorted arrayの問題にチャレンジする。昇順ソートされたリストがあり、k回時計回りに回転させた配列が与えられたときの回転数kの値を見つける問題。言葉では分かりづらいけど、言っていることは下記のとおり。
target input: {7,9,11,12,5}
min value: 5
output: 4
input soretd: {5,7,9,11,12}
↓
0 rotate: {5,7,9,11,12}
1 rotate: {12,5,7,9,11}
2 rotate: {11,12,5,7,9}
3 rotate: {9,11,12,5,7}
4 rotate: {7,9,11,12,5}*
実装
回転数が最小要素のインデックスに等しくなるなので、リニアスキャンで見つけるのであれば、とりあえず0番目の要素を一時的な最小要素として、それを比較していき、最小のものインデックスを返す方法で問題はとける。
from typing import List
def Rotation_counte(numbers: List[int]):
len_numbers = len(numbers)
min = numbers[0]
for i in range(1, len_numbers):
if min > numbers[i]:
min = numbers[i]
min_index = i
return min_index
numbers = [15, 18, 2, 3, 6, 12]
print(Rotation_counte(numbers))
print(numbers)
numbers.sort()
print(numbers)
2
[15, 18, 2, 3, 6, 12]
[2, 3, 6, 12, 15, 18]
