From cdcdacb5694d65f300205ecffc7a2cbf7188e356 Mon Sep 17 00:00:00 2001 From: akmhmgc Date: Wed, 1 Oct 2025 21:48:04 +0900 Subject: [PATCH] 33 --- 33/step1.md | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 33/step2.md | 6 ++++++ 33/step3.md | 29 +++++++++++++++++++++++++++ 33/step4.md | 1 + 4 files changed, 94 insertions(+) create mode 100644 33/step1.md create mode 100644 33/step2.md create mode 100644 33/step3.md create mode 100644 33/step4.md diff --git a/33/step1.md b/33/step1.md new file mode 100644 index 0000000..8b249f4 --- /dev/null +++ b/33/step1.md @@ -0,0 +1,58 @@ +# step1 何も見ずに解く +- 求めたいもの + - targetの候補になるものを求める。最後にtargetと一致するかどうかをチェックする。 +- どうやって範囲を狭めていくか + - leftより左はtargetではない + - rightより右はtargetではない +- 終了条件 + - left == rightとなると、rightまたはleftが答えの候補になる +- 作業 + - 中央のインデックスはmiddle = (left + right) / 2とする（切り捨て） + - 範囲の更新は以下でないと無限ループになる + - left = middle + 1 + - right = middle + - middleを含む右が昇順の時 + - targetが(middle + 1)の値以上rightの値以下の時 + - middleを含む左にtargetは存在しないのでleft = middle + 1に更新できる + - targetが(middle + 1)の値より小さい or rightの値より大きい時 + - middleより右にtargetは存在しないのでright = middleに更新できる + - ※ 「targetがmiddleの値以上rightの値以下の時」としていないのは、leftの更新によって範囲を1以上狭められないパターンが出るため + - middleを含む左が昇順の時 + - targetがleftの値以上middleの値以下の時 + - middleより左にtargetが存在しないのでright = middleに更新できる + - targetがleftより小さい or middleより大きい時 + - middleを含む左にはtargetは存在しないのでleft = middle + 1で更新できる + +考え方的に間違ってない気がするが、考えるのに疲れる… + +時間計算量はO(logN)で、空間計算量はO(1) +numsの最大サイズは10^4なので余裕で1秒以内に間に合う + +```ruby +# @param {Integer[]} nums +# @param {Integer} target +# @return {Integer} +def search(nums, target) + left = 0 + right = nums.size - 1 + while left < right + mid = (left + right) / 2 + if nums[mid] <= nums[right] + if nums[mid + 1] <= target && target <= nums[right] + left = mid + 1 + else + right = mid + end + else + if nums[left] <= target && target <= nums[mid] + right = mid + else + left = mid + 1 + end + end + end + not_existed = -1 + nums[left] == target ? left : not_existed +end +``` + diff --git a/33/step2.md b/33/step2.md new file mode 100644 index 0000000..ff743f3 --- /dev/null +++ b/33/step2.md @@ -0,0 +1,6 @@ +# step2 他の方の解答を見る + +## rotateした場所を見つけて二回二分探索する方法 +https://github.com/sakupan102/arai60-practice/pull/44 +これも思いついたが、長くなる割に分割することでわかりやすくなるものでもないのでやめた。 + diff --git a/33/step3.md b/33/step3.md new file mode 100644 index 0000000..03737df --- /dev/null +++ b/33/step3.md @@ -0,0 +1,29 @@ +# step3 3回続けて10分以内に書いてエラーを出さなければOKとする + +```ruby +# @param {Integer[]} nums +# @param {Integer} target +# @return {Integer} +def search(nums, target) + left = 0 + right = nums.size - 1 + while left < right + mid = (left + right) / 2 + if nums[mid] <= nums[right] + if nums[mid + 1] <= target && target <= nums[right] + left = mid + 1 + else + right = mid + end + else + if nums[left] <= target && target <= nums[mid] + right = mid + else + left = mid + 1 + end + end + end + not_existed = -1 + nums[left] == target ? left : not_existed +end +``` diff --git a/33/step4.md b/33/step4.md new file mode 100644 index 0000000..5941ee1 --- /dev/null +++ b/33/step4.md @@ -0,0 +1 @@ +## step4 レビューを受けて解答を修正