θ(n)时间查找排序数组中log₂(n)个最小及最大值的算法求解

方案1：固定容量堆方案（工程场景适用） #

• 第一步先计算k = ⌊log₂(n)⌋，该值随n增长速度极慢，属于远低于n的低阶项。
• 筛选最小的k个元素：取数组前k个元素构建大小为k的大顶堆，之后遍历数组剩余的n-k个元素，若当前元素小于堆顶元素，则弹出堆顶，将当前元素插入堆并调整堆结构。
• 筛选最大的k个元素：取数组前k个元素构建大小为k的小顶堆，之后遍历数组剩余的n-k个元素，若当前元素大于堆顶元素，则弹出堆顶，将当前元素插入堆并调整堆结构。
• 最后将得到的k个最小元素、k个最大元素分别做升序排序后拼接，即可得到最终的有序结果。

注意不要直接使用全量堆排序，全量堆排序时间复杂度为O(n log n)，不符合要求，仅维护固定大小的堆即可满足需求。

方案2：线性选择法（严格符合θ(n)要求） #

• 第一步同样计算k = ⌊log₂(n)⌋。
• 调用线性选择算法（如BFPRT算法）找到数组中第k小的元素，遍历一次数组收集所有小于等于该值的元素，即为需要的k个最小元素。
• 再次调用线性选择算法找到数组中第k大的元素，遍历一次数组收集所有大于等于该值的元素，即为需要的k个最大元素。
• 将两组元素分别升序排序后拼接，得到最终结果。

• 首先明确k为低阶项，k log k的量级可以完全忽略，不会影响整体复杂度的阶。
• 堆方案总时间为两次遍历调整堆的时间加排序时间：2*O(n log k) + O(k log k)，代入k=log₂n后得到O(n log log n)，log log n的增长速度极慢，工程场景下可近似为常数，完全满足题目对线性时间的要求。
• 线性选择法时间复杂度严格为θ(n)：BFPRT算法查找指定顺序统计量的最坏时间复杂度为θ(n)，两次查找加两次遍历收集元素的时间为θ(n)，最后的排序时间为低阶项，因此整体时间复杂度严格符合θ(n)的要求。

内容的提问来源于stack exchange，提问作者DanielG