求解n个元素中第k大的元素

Question

这一节讲的使用快速排序的思想来求解时间复杂度是O(n),但是使用一个容量最大为k的最小堆来求解，时间复杂度是O(nlogk)，因为k是常数，所以其复杂度都是O(n),那么两种解法哪个更优，在各种情况下更优呢？

Answer 1

liuyubobobo 2019-10-27 10:21:48

使用堆的优点是，不需要一次性知道所有数据，数据可以一点一点流入堆。同时，堆中相当于保持的是当下已知数据的 top k。这在很多场景下都是很有意义。

继续加油！：）