這是一個可以在保證線性時間(c++ std::nth_element是隨機演算法)找出一個序列中第k大元素的演算法,網路上已經有不少教學,但是很多人都認為常數太大因此缺乏實作。
教學文在此:http://tmt514-blog.logdown.com/posts/484313-divide-and-conquer-method-iii-find-the-median
其實我高中時就想要試著去時做看看,但是因為那時的程式能力太差的關係,做出來的東西一直有bug,後來去忙其他事情後就被我忘掉了。最近因為學長面試有被問到一樣的問題跑來問我,才慢慢想起來有一份沒寫完的code,於是今天抱著不管怎樣都要寫出來的精神把他寫完了:
沒有留言:
張貼留言