大厂面试：找出数组中第k大的数的最佳算法

副标题：从暴力到最优，一次性掌握这道高频算法题的降维打击思路。

开篇痛点引入

“又挂了！面了五家公司，三道都问‘找出第K大的数’！” 深夜，程序员小李对着屏幕哀叹。这道题看似简单，却暗藏杀机——它不仅是面试高频“钉子户”，更能瞬间区分出你是背题侠还是真懂哥。

今天，我们不背答案，而是打通任督二脉。掌握这五种递进式解法，下次面试官再问，你可以从容反问：“您想听O(n log n)、O(n)还是最省内存的解法？”

第一层：暴力排序法（新手村）

这是最直觉的方法：直接把数组排序（列如快排），然后取第 k 个元素。

def findKthLargest(nums, k):
    nums.sort()
    return nums[-k]

复杂度：时间 O(n log n)，空间 O(1)。

点评：简单粗暴，适合小数据。但面试只答这个，大致率会听到：“还有更优解吗？”

第二层：堆的妙用（高手的选择）

维护一个大小为 k 的小顶堆。遍历数组，堆里只保留当前最大的 k 个数，堆顶就是第 k 大的数。

import heapq
def findKthLargest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap) # 弹出最小的
    return heap[0]

复杂度：时间 O(n log k)，空间 O(k)。

精髓：不必全排序，在海量数据（无法全部装入内存）中找Top K时，此法是标准答案。

第三层：快速选择算法（内功心法）

这是快速排序的“近亲”——快速选择。我们并不需要让整个数组有序，只需要让某个基准值到达其正确位置，并判断这个位置是否是我们要找的 k。

import random
def findKthLargest(nums, k):
    def quick_select(left, right, k_smallest):
        # 递归选择基准值
        pivot_index = random.randint(left, right)
        pivot_index = partition(left, right, pivot_index)
        if k_smallest == pivot_index:
            return nums[k_smallest]
        elif k_smallest < pivot_index:
            return quick_select(left, pivot_index - 1, k_smallest)
        else:
            return quick_select(pivot_index + 1, right, k_smallest)
    # 第k大 = 第 (n-k) 小
    return quick_select(0, len(nums)-1, len(nums)-k)

复杂度：平均 O(n)，最坏 O(n²)（但随机化基准值可避免）。

价值：这是理论上的最优解之一，能展现你对经典算法的深刻理解。

第四层：BFPRT算法（面试核武）

快速选择的缺陷在于最坏情况。而BFPRT算法（又称中位数的中位数算法）通过精心选择基准值，能将最坏时间复杂度严格保证在 O(n)。

核心思想：

将数组每5个一组分组。

找出每组的中位数。

递归调用自身，找出这些中位数的中位数作为基准值。

用此基准值进行划分。

# 代码较长，体现的是严谨的算法设计思想

何时用：当面试官追问“如何避免最坏情况”时，抛出此名，就是绝对的加分项。它证明了你不满足于“平均优秀”，追求的是确定性的卓越。

第五层：场景化决策（工程思维）

真正的工程高手，会根据数据特点选择武器：

数据流 & 海量数据：用堆（解法二）。

数据可全内存、追求平均速度：用快速选择（解法三）。

对延迟敏感、要求绝对稳定：思考BFPRT（解法四）。

数据范围有限：甚至可以用计数排序，达到 O(n) 时间。

一句话总结：算法没有银弹，只有最适合场景的武器。

结语：从一道题到一类题

“找第K大的数”不是一个孤立的题目。它关联着：

Top K 问题（堆）

快速排序思想（分治）

期望与最坏复杂度分析（随机化）

海量数据处理思想（外排序、堆）

掌握它，你就打通了算法面试的一条重大脉络。下次面试，请带着选择权进场。

本文关键词： #算法面试 #TopK问题 #快速选择 #程序员内功 #时间复杂度

互动话题：你在面试中还遇到过哪些“一道题考多个知识点”的经典题？评论区聊聊！

彩蛋：

一.前置条件

如果数组为a,大小为n，要找到数组a中第k大的数。

二.解决方案

1.使用任意一种排序算法（例如快速排序）将数组a进行从大到小的排序，则第n-k个数即为答案。

2.构造一个长度为k的数组，将前k个数复制过来并降序排序。然后依次将 k+1 到 n 位的数分别插入 k 长度的数组中并保持数组长度为k且降序排列。最终长度为k的数组的最后一个元素即是答案。

3.将数组的所有元素构造一个大顶堆，然后删除堆顶元素k次并重新构成大顶堆，则第k次操作后的堆顶元素即为答案。

4.用快速排序的思想不把数组元素全排序的优化算法。

1）先看一下快速排序（降序排序）的算法。

/**
快速排序主函数
a：要排序的数组
left：排序数组左边界索引
right：排序数组右边界索引
*/
public void quickSort(int a[], int left, int right) {
  if (left < right) {
//算出基准元素索引值index
     int index = partition(a, left, right);
//对低于index索引的数组递归排序
     quickSort(a, left, index - 1);
//对高于index索引的数组递归排序
     quickSort(a, index + 1, right);
  }




}




//算出基准元素索引值，此索引值左侧值都大于基准元素值，此索引值右侧值都小于基准元素值
public int partition(int[] num, int left, int right) {
   if (num == null || num.length <= 0 || left < 0 || right >= num.length) {
      return0;
   }
//获取数组基准元素的下标
    int prio = num[left + (right - left) / 2]; 
//从两端交替向中间扫描  
    while (left <= right) {                 
       while (num[left] > prio)
          left++;
       while (num[right] < prio)
          right--;
       if (left <= right) {
//将不符合条件的元素值交换位置并继续扫描
          swap(num, left, right);        
          left++;
          right--;
        }
    }
   return left;
}




//交换元素
public void swap(int[] num, int left, int right) {
    int temp = num[left];
    num[left] = num[right];
    num[right] = temp;
}

2）我们选择数组区间 a[0…n-1]的中间位置的一个元素 a[n/2]作为 pivot，对数组 a[0…n-1]进行分区，这样数组就分成了三部分，a[0…p-1]、a[p]、a[p+1…n-1]。

如果 p+1=k，那 a[p]就是要求解的答案；如果 k>p+1, 说明第 k 大元素出目前 a[p+1…n-1]区间，我们再按照上面的思路递归的在 a[p+1…n-1]这个区间内查找。同理，如果 k<p+1，那就在 a[0…p-1]区间内递归查找。

3）所以改善后的代码如下：

public int quickSortKthLargest(int a[], int left, int right, int k) {
   if (left < right) {
//算出基准元素索引值index
      int index = partition(a, left, right);
//索引对应的值就是第k大的数
      if(index+1==k){
         return a[index];
      }
//在索引左边继续查找
      elseif(index+1>k){
         return quickSortKthLargest(a, left, index-1, k);
      } 
//在索引右边继续查找
      else{
        return quickSortKthLargest(a, index+1, right, k);
       }


   }else{
     return -1;
  }




}

5.在Python中，我们可以使用内置的heapq库来查找数组的第k大元素。heapq库实现了一个堆数据结构，我们可以利用堆的性质来找到数组的第k大元素。

代码如下：

# 返回第k大元素
def get_kth_largest(a, k):
# heapq.nlargest(k, a)会返回数组a中最大的k个元素，
# 然后我们通过[-1]来取得这k个元素中的最后一个，也就是第k大的元素。
  return heapq.nlargest(k, a)[-1]

6.使用最小堆来查找第k大的元素。

第一构建一个空的最小堆。遍历数组a，如果堆的大小小于k，我们就把当前元素加入堆中。如果堆的大小已经达到了k，我们就比较当前元素和堆顶元素（也就是堆中的最小元素），如果当前元素大于堆顶元素，我们就把堆顶元素替换为当前元素，再重新调整最小堆结构。这样，当遍历完整个数组后，堆顶元素就是数组的第k大元素（即是大小为k的最小堆（保存了数组中的最大的k个数）的最小元素）。

代码如下：

def get_kth_largest(a, k):
    heap = []  
    for num in a:  
# 若最小堆大小小于k，则将元素插入最小堆
    if len(heap) < k:  
      heapq.heappush(heap, num)  
    else:  
# 若元素大于最小堆堆顶元素，则插入最小堆并重新排列
      if num > heap[0]:  
         heapq.heapreplace(heap, num)  
# 堆顶元素即为数组的第k大元素
    return heap[0]