【面经】算法相关

baseline：

用堆，如果取最大的K个，就用最小堆，遍历数组，遇到比堆顶元素大的元素就入堆，同时堆中元素超过k个需要poll操作，保证堆中只有K个元素，最终的topk元素在堆中。

时间复杂度分析:

$O(n*logk)$$ ，元素入堆复杂度$$O(logk)$

$O(n)$ 算法：

先用quick select方法找到第K大的元素，复杂度 $O(n)$

然后再遍历一遍，将大于K的元素取出，复杂度 $O(n)$

总复杂度 $O(n)$

！！！！！卧槽！神奇！！！！

follow up：海量数据选取第K大

Quick Select，详见【九章算法强化班】两指针

时间复杂度 $O(n)$

海量数据排序怎么做？

baseline：快排，问题：数据量很大，内存根本存不下，不可行

桶排序：

将数据分桶，每个桶存入一个文件，然后文件内部有序，取出合并的时候可以用K路归并，优化：k路可以建个堆