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