98.数组中的第K个最大元素

题目

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

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

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

示例 2:

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

思路

方法一：排序法(最简单，但不是最快的)

fun findKthLargest(nums: IntArray, k: Int): Int {
    nums.sort()  // 升序排序
    return nums[nums.size - k]  // 倒数第k个
}

时间复杂度:O(nlogn) -- 排序的代价

方法二:最小堆法

用一个大小为k的最小堆，堆里保存目前最大的k个数，堆顶就是第k大的数。

为什么用最小堆？ - 最小堆的堆顶是堆中最小的元素
- 我们维护一个大小为k的堆，里面放着当前最大的k个数 - 堆顶就是这k个数中最小的那个 -- 也就是第k大的数

怎么维护？

• 遍历每个数，如果堆还没满，直接加入
• 如果堆满了，且当前数比堆顶大，就把堆顶弹出，加入当前数
• 最后堆顶就是答案

fun findKthLargest(nums: IntArray, k: Int): Int {
    // 创建一个最小堆
    val minHeap = PriorityQueue<Int>()

    for (num in nums) {
        minHeap.offer(num)
        // 如果堆的大小超过k，移除堆顶（最小的元素）
        if (minHeap.size > k) {
            minHeap.poll()
        }
    }

    // 堆顶就是第k大的元素
    return minHeap.peek()
}

时间复杂度：O(n log k) — 每次入堆出堆都是O(log k)

方法三：快速选择法(最快)

基于快速排序的partition思想，但只递归一边，不像快排两边都要递归。

核心思想：

1. 随便选一个数作为"基准"

2. 把比基准大的放左边，比基准小的放右边

3. 看基准现在在第几位

   • 如果正好是第k位 → 返回
   • 如果比k大 → 去左边找
   • 如果比k小 → 去右边找

fun findKthLargest(nums: IntArray, k: Int): Int {
    val n = nums.size
    // 第k大 = 第n-k小（在升序排列中的位置）
    return quickSelect(nums, 0, n - 1, n - k)
}

private fun quickSelect(nums: IntArray, left: Int, right: Int, kSmallest: Int): Int {
    if (left == right) return nums[left]

    // partition：选一个基准，把数组分成两部分
    val pivotIndex = partition(nums, left, right)

    return when {
        kSmallest == pivotIndex -> nums[pivotIndex]
        kSmallest < pivotIndex -> quickSelect(nums, left, pivotIndex - 1, kSmallest)
        else -> quickSelect(nums, pivotIndex + 1, right, kSmallest)
    }
}

private fun partition(nums: IntArray, left: Int, right: Int): Int {
    // 选最右边的元素作为基准
    val pivot = nums[right]
    var i = left  // i指向"比基准小的区域"的末尾

    for (j in left until right) {
        if (nums[j] <= pivot) {
            // 交换
            val temp = nums[i]
            nums[i] = nums[j]
            nums[j] = temp
            i++
        }
    }

    // 把基准放到正确的位置
    nums[right] = nums[i]
    nums[i] = pivot

    return i
}

复杂度

• 时间复杂度:
• 空间复杂度:

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!