关于查找数组中最小的k个元素的解答、updated

关于查找数组中最小的k个元素的全面讨论与解答

原文以上的内容已删。因为我觉得，讨论的乱七八糟，漏洞百出。忘读者见谅。这个关于寻找最小的k个元素的问题，在程序员面试题狂想曲系列中，马上会有所彻底的阐述。敬请期待。

litaoye：
其实LZ完全不必动摇，Nth Element绝对是O(n)的，不是n*log(k)的，跟k没什么关系。Nth Element选数的时候用随机好了，不至于出现最坏的情况，另外算法导论中还讲到的那种取5个数求中位数的方法，可以证明最坏情况下也是O(n)的。（正解）

updated：

关于寻找数组中最小的k个元素的问题，已在程序员面试题狂想曲：第三章、寻找最小的k个数、updated 10次，进行彻底而深入的阐述。谢谢。

完。

---

版权所有。转载本BLOG内任何文章，请以超链接形式注明出处。