数组中的第K个最大元素：算法实现与性能分析

问题背景

在算法面试和实际编程中，找出数组中第K大的元素是一个常见且经典的问题。本文将深入探讨该问题的两种主要解决方案：快速选择算法和堆排序方法。

问题描述

给定一个未排序的整数数组 nums 和一个整数 k，要求找出数组中第 k 个最大的元素。注意，这里的"第k大"意味着排序后从大到小的第k个位置。

算法挑战

• 时间复杂度要求：尽可能接近O(n)
• 空间复杂度要求：尽可能低
• 需要处理边界情况，如 k 大于数组长度

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

算法原理

快速选择算法是快速排序的变体，其核心思想是：

1. 选择一个基准元素
2. 将数组划分为两部分
3. 根据划分后基准元素的位置，决定是否需要递归处理左半部分或右半部分

代码实现

class Solution {
public:
    int quick_partition(vector<int>& nums, int left, int right, int k) {
        int l = left, r = right;
        // 随机选择基准元素，避免最坏情况
        swap(nums[left], nums[rand()%(right-left+1)+left]);
        
        while (l < r) {
            // 从右向左找第一个小于基准的元素
            for (; l < r && nums[r] >= nums[left]; r--);
            // 从左向右找第一个大于基准的元素  
            for (; l < r && nums[l] <= nums[left]; l++);
            
            // 交换这两个元素
            swap(nums[l], nums[r]);
        }
        
        // 将基准元素放到正确的位置
        swap(nums[l], nums[left]);
        
        // 根据当前位置判断下一步处理
        if (l == nums.size() - k) {
            return nums[l];
        }
        else if (l < nums.size() - k) {
            // 目标在右半部分
            return quick_partition(nums, l + 1, right, k);
        }
        else {
            // 目标在左半部分  
            return quick_partition(nums, left, l - 1, k);   
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        if (k > nums.size()) {
            return -1;
        }
        return quick_partition(nums, 0, nums.size() - 1, k);
    }
};

算法优化

1. 随机选择基准元素：通过 rand() 随机选择，避免快排的最坏情况
2. 递归处理：仅处理包含目标元素的子数组，提高效率

时间复杂度分析

• 平均时间复杂度：O(n)
• 最坏时间复杂度：O(n²)（极小概率）
• 空间复杂度：O(log n)（递归栈空间）

解决方案二：堆排序方法

算法原理

利用优先队列（堆）维护当前最大的K个元素，队首即为第K大元素。

代码实现

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if (k > nums.size()) {
            return -1;
        }
        
        // 小根堆，保存最大的k个元素
        priority_queue<int, vector<int>, greater<int>> small_heap;
        
        for (int i = 0; i < nums.size(); i++) {
            if (i < k) {
                // 前k个元素直接入堆
                small_heap.push(nums[i]);
            }
            else {
                // 若新元素大于堆顶，则替换堆顶元素
                if (nums[i] > small_heap.top()) {
                    small_heap.push(nums[i]);
                    small_heap.pop();
                }
            }
        }
        
        return small_heap.top();
    }
};

算法特点

1. 使用 priority_queue 的 greater<int> 创建小根堆
2. 堆的大小始终保持在K
3. 时间复杂度为 O(n * log k)

时间复杂度分析

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

算法对比

总结

通过快速选择和堆排序两种方法，我们成功解决了"数组中第K大元素"问题。选择算法时，需根据具体的数据规模和性能要求进行权衡。

参考资料

• LeetCode 215题：数组中的第K个最大元素
• 快速选择算法详解
• 堆排序算法原理