咨询：单次读取数组求k个最小元素的线性时间算法方案

核心思路 #

利用大小为5k的数组B维护候选元素集，结合Median of Medians快速筛选出不可能属于全局前k小的元素，全程仅遍历A一次，同时保证线性时间复杂度。

算法步骤 #

1. 初始化候选集

   • 读取数组A的前5k个元素，存入数组B中。

2. 迭代筛选候选集

   • 当B的元素数量达到5k时：
     1. 用Median of Medians算法在O(k)时间内找到B中的第k小元素p。
     2. 过滤B，仅保留所有小于等于p的元素。此时B的元素数量最多为4k（因为至少有k个元素大于p会被丢弃）。
     3. 继续读取A中剩余的元素：
        • 若当前元素x ≤ p，将x加入B；
        • 若x > p，直接丢弃（x不可能属于全局前k小的元素）。
   • 重复上述过程，直到A的所有元素被读取完毕。

3. 生成最终结果

   • 对B中的元素进行排序，取前k个元素，即为数组A的k个最小元素。

正确性与复杂度证明 #

• 正确性：假设存在一个全局前k小的元素x被过滤，那么x > p（p是某次筛选的第k小元素）。但此时B中已有至少k个元素≤p，加上x的话，全局中≤x的元素至少有k+1个，与x属于前k小矛盾。因此所有目标元素都会被保留在B中。
• 时间复杂度：
  • 每次筛选B的时间为O(k)，每次筛选后B至少减少k个元素，因此筛选次数为O(n/k)，总筛选时间为O(n/k * k) = O(n)。
  • 最后排序B的时间为O(k log k)，由于k < n，这部分时间属于O(n)量级。
  • 整体时间复杂度为O(n)，符合要求。
• 内存限制：B的大小始终不超过5k，满足题目给定的内存限制。
• 读取限制：每个A中的元素仅被读取一次，无写入或交换操作，符合要求。

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