LeetCode 215：数组中的第K个最大元素 - 两种高效解法详解

在算法面试中，查找数组中第K个最大元素是一个经典问题。LeetCode第215题要求我们在未排序的数组中找到第K大的元素。本文将介绍两种高效的解决方案：快速选择算法和堆（优先队列）方法，帮助你全面掌握这道高频面试题。

问题描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1：

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2：

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

注意： 可以假设 k 总是有效的，即 1 ≤ k ≤ nums.length。

解法一：快速选择算法（QuickSelect）

算法思想

快速选择算法基于快速排序的分区思想，通过每次分区将数组分为两部分，然后根据目标位置选择继续分区其中一侧，从而在平均 O(n) 的时间复杂度内解决问题。

算法步骤

1. 随机选择枢轴：为了避免最坏情况，随机选择一个元素作为枢轴
2. 分区操作：
   • 将大于枢轴的元素移到左侧
   • 将小于等于枢轴的元素移到右侧
3. 比较枢轴位置：
   • 如果枢轴位置正好是k-1，返回该元素
   • 如果位置大于k-1，在左半部分继续查找
   • 如果位置小于k-1，在右半部分继续查找

Java实现

import java.util.Random;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int left = 0;
        int right = nums.length - 1;
        int targetIndex = k - 1; // 第k大元素在降序数组中的索引
        Random rand = new Random();
        
        while (left <= right) {
            // 随机选择枢轴并交换到末尾
            int pivotIndex = left + rand.nextInt(right - left + 1);
            swap(nums, pivotIndex, right);
            
            // 分区操作，返回枢轴最终位置
            int partitionIndex = partition(nums, left, right);
            
            if (partitionIndex == targetIndex) {
                return nums[partitionIndex];
            } else if (partitionIndex > targetIndex) {
                right = partitionIndex - 1;
            } else {
                left = partitionIndex + 1;
            }
        }
        return -1; // 理论上不会执行到这里
    }
    
    // 分区函数：将大于枢轴的元素移到左侧
    private int partition(int[] nums, int left, int right) {
        int pivot = nums[right];
        int i = left;
        
        for (int j = left; j < right; j++) {
            if (nums[j] > pivot) {
                swap(nums, i, j);
                i++;
            }
        }
        swap(nums, i, right);
        return i;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

复杂度分析

• 时间复杂度：
  • 平均情况：O(n)
  • 最坏情况：O(n²)（但随机枢轴有效避免最坏情况）
• 空间复杂度：O(1)

算法特点

1. 原地操作，不需要额外空间
2. 平均性能优异
3. 会修改原始数组

解法二：最小堆（优先队列）

算法思想

使用最小堆维护数组中最大的k个元素。堆顶元素（最小值）即为第k大的元素。

算法步骤

1. 初始化大小为k的最小堆
2. 遍历数组：
   • 当堆大小小于k时，直接添加元素
   • 当堆已满且当前元素大于堆顶时，替换堆顶元素
3. 遍历结束后，堆顶元素即为结果

Java实现

import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 创建最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        for (int num : nums) {
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else if (num > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(num);
            }
        }
        
        return minHeap.peek();
    }
}

复杂度分析

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

算法特点

1. 不修改原始数组
2. 适合处理流式数据
3. 代码简洁易懂
4. 时间复杂度稳定

两种解法比较

测试示例

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        int[] nums1 = {3, 2, 1, 5, 6, 4};
        int k1 = 2;
        System.out.println("示例1: " + solution.findKthLargest(nums1, k1)); // 5
        
        int[] nums2 = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        int k2 = 4;
        System.out.println("示例2: " + solution.findKthLargest(nums2, k2)); // 4
        
        int[] nums3 = {7, 6, 5, 4, 3, 2, 1};
        int k3 = 3;
        System.out.println("示例3: " + solution.findKthLargest(nums3, k3)); // 5
    }
}

总结

LeetCode 215题"数组中的第K个最大元素"有两种高效解法：

1. 快速选择算法：

   • 优点：平均时间复杂度O(n)，空间复杂度O(1)
   • 缺点：最坏情况O(n²)，修改原数组
   • 适用场景：空间要求高，可接受修改数组

2. 最小堆方法：

   • 优点：时间复杂度稳定O(n log k)，不修改原数组
   • 缺点：空间复杂度O(k)
   • 适用场景：流式数据，需要保持原数组不变

根据具体问题场景选择合适的解法：

• 对于内存敏感的场景，优先选择快速选择算法
• 对于需要保持原数组或处理流式数据的场景，选择最小堆方法

掌握这两种解法及其适用场景，可以帮助你在面试中灵活应对不同变种问题。