Re: [問題] LeetCode 378. Kth Smallest Element...

作者: alan23273850   2017-08-07 13:34:34
我們演算法老師說過對於一些比較常用、有名的算法,通常已經有先人發展出漂亮的寫法
我們的任務就是找出漂亮、優美的寫法,理解它,然後背起來!
雖然老師那個時候是拿 qsort 當例子,但是我想 binary search 也是一樣的。
這是我去年複習的時候寫的投影片中的其中一頁:
https://i.imgur.com/nQ0BU9B.jpg
我是覺得這樣的寫法還是比較好理解
至於遇到多重相同值元素時可以一直往前找,就能碰到第一個出現的元素,
相對地如果要最後一個元素就一直往後找就好!
另外,我自己是感覺這種著名算法未必要很堅持的看懂其他人的寫法,
因為這種小細節往往是會花最多時間的地方,其實只要自己會寫、寫得出來就好。
當然能快速看懂一個人的 code 是種超能力,但如果是為了訓練這種能力而花時間
在這種小細節上,CP 值恐怕不高。(花太多時間,卻只提升一點點能力)
作者: FRAXIS (喔喔)   2017-08-07 21:27:00
按這樣實作法 怎麼實現 C++ 的 lower_bound?時間要O(lg n)
作者: shaopin (Brian)   2017-08-08 09:43:00
不是只要在corner case上注意一下就可以變成lower or upper bound了嗎?

Links booklink

Contact Us: admin [ a t ] ucptt.com