いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 153 find-minimum-in-rotated-sorted-array

投稿日:

こんにちは

今回の学びは

へー、バイナリーサーチって、rotateされていても使えるんだ

 

問題は。。。

(時間配分は5分問題理解 10分検討 10分実装  20分振り返り の一文45分構成)

まずは入出力をしっかりおさえましょう。

 

 

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

・。・ binary searchはrotateされててもできて、ひたすら小さい方によせていけばいい

 

 

なんか、問題の意味がわからんかったけど

これでいいのって、感じで提出したら通る。なんだ、なんだ。

O(n)でというているし、

逆にbinary searchのほうがO(nlogn)で遅いでしょ?

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/discuss/394859/very-simple-python-code-Binary-Search

んな感じでやってくれてますけど

へー、バイナリーサーチって、rotateされていても使えるんだ

 

っていうのが大きな。

むしろそうじゃないと使える気がしなかったらからスルーしてたわ。

こっちら自称 O(n)ソリューションで

 

 

こちらが、binary searchアプローチで結果、かわりませんでした。

なんで!?まぁ、入力が小さめであんまり差がでなかったてことで。

まとめ

へー、バイナリーサーチって、rotateされていても使えるんだ

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.