肥死不可一面挂经

T大农民伯伯 发表于 2018-10-27 04:03
其实你说klogn也是可以的。先建堆，再吐k个元素

我还真说了klogn。。突然发现klogn比nlogk更快耶===但还是挂了

论坛匿名用户 发表于 2018-10-27 04:22
我还真说了klogn。。突然发现klogn比nlogk更快耶===但还是挂了

不好的地方大概是klog n用的空间更多一些。

谢谢楼主分享的面经

T大农民伯伯 发表于 2018-10-27 04:30
不好的地方大概是klog n用的空间更多一些。

请问有klogn 和 nlogk两种情况吗？能简单说明下吗？为什么klogn用的空间更多呢？谢谢！

木木木一 发表于 2018-10-28 11:30
请问有klogn 和 nlogk两种情况吗？能简单说明下吗？为什么klogn用的空间更多呢？谢谢！

nlog k的做法是建立大小为ｋ的堆，把ｎ个元素往里面塞同时往外面排。ｋlogn　是先建立大小为ｎ的堆，往外面排ｋ个元素。

T大农民伯伯 发表于 2018-10-30 07:38
nlog k的做法是建立大小为ｋ的堆，把ｎ个元素往里面塞同时往外面排。ｋlogn　是先建立大小为ｎ的堆，往外 ...

建堆是O(N)，K次调整是O(KlgN)，总共O(N+KlgN)

多谢lz分享