如何设计O(n)时间复杂度算法找出数组中2^k级最大元素？

针对需要找出数组中第1、2、4、8…直到2^logn大元素的需求，这里提供一个严格O(n)时间复杂度的实现方案：

核心思路 #

利用快速选择的分区特性，批量处理所有目标位置（1、2、4…这些指数增长的k值）。每次分区后，把不同的k值分配到对应的子数组中继续查找，由于k值是指数级增长，每一轮处理的数组大小会快速缩小，总操作量控制在O(n)范围内。

具体步骤 #

1. 确定目标位置列表 #

先算出所有符合要求的k值：从1开始，每次乘2，直到k不超过数组长度n。比如n=10时，目标k是[1,2,4,8]。

2. 分区查找（迭代/递归均可） #

实现一个函数，输入当前处理的子数组和需要查找的k子集，返回这些k对应的元素：

• 分区操作：任选一个基准值（pivot），把当前数组分成三部分：比基准大的元素、等于基准的元素、比基准小的元素。
• 分配k值：
  • 如果某个k小于等于「比基准大的元素数量」，说明这个k对应的元素在「比基准大」的子数组里，后续处理这个子数组。
  • 如果k在「比基准大的数量」到「比基准大+等于基准的数量」之间，说明这个k对应的元素就是基准值。
  • 如果k大于前两者的和，说明这个k对应的元素在「比基准小」的子数组里，后续处理这个子数组时，要把k减去前两者的和（因为前面已经排除了这么多更大的元素）。
• 合并结果：把分配好的k子集分别传入对应的子数组处理，最后合并所有结果。

3. 收集结果 #

按目标k的顺序，从函数返回的结果中提取对应元素，就是我们要找的各个幂次大元素。

复杂度证明 #

每次分区的时间是当前子数组的长度，而由于k是指数增长，每一轮处理的子数组大小最多是上一轮的一半，总操作量是n + n/2 + n/4 + ... = 2n，也就是O(n)，完全符合要求。

示例验证 #

比如数组是[10,9,8,7,6,5,4,3,2,1]，n=10：

• 第一次选基准5，分成大于5的[10,9,8,7,6]、等于5的[5]、小于5的[4,3,2,1]
• 目标k中1、2、4都小于等于5（大于5的元素数量），所以去大于5的子数组找；k=8大于5+1=6，所以去小于5的子数组找k'=8-5-1=2
• 处理大于5的子数组时，选基准8，分成大于8的[10,9]、等于8的[8]、小于8的[7,6]
  • k=1、2去大于8的子数组找，得到第1大10、第2大9；k=4大于2+1=3，去小于8的子数组找k'=1，得到第4大7
• 处理小于5的子数组时，找k'=2，得到第8大3
• 最终结果就是[10,9,7,3]，和实际排序结果一致。

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