NeetCodeのSolutionを書いていく #
Search in Rotated Sorted Array #
https://neetcode.io/problems/find-target-in-rotated-sorted-array
neetcode.io
問題 #
長さnの配列が与えられます。もともと昇順でソートされていたものです。 今、1~nの間で回転されました。 一緒に整数targetが与えられます。 targetのindexか、存在しない場合は-1を返しなさい。 numsの要素はユニークです。 計算量O(n)の回答では当たり前過ぎます。O(logn)でできますか？
制約 #
- 1 <= nums.length <= 1000
- -1000 <= nums[i] <= 1000
- -1000 <= target <= 1000
計算量：O(logn) メモリ：O(1)
例 #
Input: nums = [3,4,5,6,1,2], target = 1 Output: 4
Input: nums = [3,5,6,0,1,2], target = 4 Output: -1
メモ #
前回の問題と似ていそう。
from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> int:
# ローテーションすると、最初の状態(0回ローテーション)以外で、昇順ソートされた配列が２つ存在する状態になる。
# 配列の一番左をl、右をr、真ん中をmとする。
# この時 target == nums[l]ならlをtarget == nums[m]ならmをtarget == nums[r]ならrを返す。
# nums[l] > nums[m] の場合、lとmは異なるソート配列に存在する。
# この時target < nums[m] の場合は、l~mにtargetが存在する可能性があるので、rをmにする。
# そうではない場合で、nums[m] < target < nums[r] の場合は m~rにtargetが存在する可能性があるので、lをmにする。
# それ以外の場合はtargetは存在しないので-1を返す。
# それ以外の場合は、lとmは同じソート配列に存在する。
# この時 nums[l] < target < nums[m]の場合は、l~mにtargetが存在する可能性があるので、rをmにする。
# そうではない場合は、m~rにtargetが存在する可能性があるので、lをmにする。
# mを(l+m)//2にする。
# 上記を繰り返す
l = 0
r = len(nums) - 1
while l <= r:
m = (l + r) // 2
if target == nums[l]:
return l
elif target == nums[m]:
return m
elif target == nums[r]:
return r
if nums[l] > nums[m]:
if nums[m] < target and target < nums[r]:
l = m + 1
else:
r = m - 1
else:
if nums[l] < target and target < nums[m]:
r = m - 1
else:
l = m + 1
return -1