Medium

题目描述

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

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

你能否不使用排序来解决这个问题？

示例 1：

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

示例 2：

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

提示：

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

解题思路

这道题有多种解法，我们来分析几种常见的思路：

方法一：直接排序（最简单）

将数组排序后直接返回第k个最大元素。时间复杂度O(nlogn)。

方法二：最小堆（推荐）

维护一个大小为k的最小堆，遍历数组时：

  • 如果堆大小小于k，直接加入元素
  • 如果当前元素大于堆顶，弹出堆顶并加入当前元素

最终堆顶就是第k大元素。这种方法空间复杂度为O(k)，时间复杂度O(nlogk)，当k较小时效率很高。

方法三：快速选择算法（最优）

基于快排的分区思想，通过分区操作将数组分为两部分，如果分区点正好是第k大位置就返回，否则在对应的一侧继续查找。平均时间复杂度O(n)，最坏情况O(n²)。

考虑到实现复杂度和稳定性，推荐使用最小堆方法。

代码实现

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minHeap;
        
        for (int num : nums) {
            if (minHeap.size() < k) {
                minHeap.push(num);
            } else if (num > minHeap.top()) {
                minHeap.pop();
                minHeap.push(num);
            }
        }
        
        return minHeap.top();
    }
};

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        import heapq
        
        min_heap = []
        
        for num in nums:
            if len(min_heap) < k:
                heapq.heappush(min_heap, num)
            elif num > min_heap[0]:
                heapq.heapreplace(min_heap, num)
        
        return min_heap[0]

public class Solution {
    public int FindKthLargest(int[] nums, int k) {
        var minHeap = new PriorityQueue<int, int>();
        
        foreach (int num in nums) {
            if (minHeap.Count < k) {
                minHeap.Enqueue(num, num);
            } else if (num > minHeap.Peek()) {
                minHeap.Dequeue();
                minHeap.Enqueue(num, num);
            }
        }
        
        return minHeap.Peek();
    }
}

var findKthLargest = function(nums, k) {
    const minHeap = [];
    
    const heapifyUp = (index) => {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (minHeap[parentIndex] <= minHeap[index]) break;
            [minHeap[parentIndex], minHeap[index]] = [minHeap[index], minHeap[parentIndex]];
            index = parentIndex;
        }
    };
    
    const heapifyDown = (index) => {
        while (2 * index + 1 < minHeap.length) {
            let smallerIndex = 2 * index + 1;
            if (2 * index + 2 < minHeap.length && minHeap[2 * index + 2] < minHeap[smallerIndex]) {
                smallerIndex = 2 * index + 2;
            }
            if (minHeap[index] <= minHeap[smallerIndex]) break;
            [minHeap[index], minHeap[smallerIndex]] = [minHeap[smallerIndex], minHeap[index]];
            index = smallerIndex;
        }
    };
    
    for (const num of nums) {
        if (minHeap.length < k) {
            minHeap.push(num);
            heapifyUp(minHeap.length - 1);
        } else if (num > minHeap[0]) {
            minHeap[0] = num;
            heapifyDown(0);
        }
    }
    
    return minHeap[0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
最小堆O(n log k)O(k)
直接排序O(n log n)O(1)
快速选择O(n) 平均，O(n²) 最坏O(1)

相关题目