力扣第215题“数组中的第K个最大元素”

在本篇文章中，我们将详细解读力扣第215题“数组中的第K个最大元素”。通过学习本篇文章，读者将掌握如何使用快速选择算法和堆排序来解决这一问题，并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释，以便于理解。

问题描述

力扣第215题“数组中的第K个最大元素”描述如下：

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

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

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

解题思路

方法一：快速选择（Quickselect）

初步分析：
- 快速选择算法是一种基于快速排序的选择算法，用于在无序列表中查找第 k 小（或大）元素。
- 快速选择通过划分操作将数组分成两部分，一部分大于等于基准元素，另一部分小于基准元素。
步骤：
- 使用快速选择算法对数组进行划分，找到第 k 个最大的元素。
- 定义一个辅助函数 partition 用于划分数组。
- 根据基准元素的位置，与 k 进行比较，决定递归的方向。

代码实现

def findKthLargest(nums, k):
    def partition(left, right):
        pivot = nums[right]
        p = left
        for i in range(left, right):
            if nums[i] <= pivot:
                nums[i], nums[p] = nums[p], nums[i]
                p += 1
        nums[p], nums[right] = nums[right], nums[p]
        return p

    def quickselect(left, right, k_smallest):
        if left == right:
            return nums[left]
        
        pivot_index = partition(left, right)
        if k_smallest == pivot_index:
            return nums[k_smallest]
        elif k_smallest < pivot_index:
            return quickselect(left, pivot_index - 1, k_smallest)
        else:
            return quickselect(pivot_index + 1, right, k_smallest)
    
    return quickselect(0, len(nums) - 1, len(nums) - k)

# 测试案例
print(findKthLargest([3,2,1,5,6,4], 2))  # 输出: 5
print(findKthLargest([3,2,3,1,2,4,5,5,6], 4))  # 输出: 4

方法二：堆排序

初步分析：
- 使用最小堆可以高效地找到第 k 个最大的元素。
- 维护一个大小为 k 的最小堆，堆顶元素即为第 k 个最大的元素。
步骤：
- 将数组的前 k 个元素插入最小堆。
- 遍历剩余的元素，如果元素大于堆顶元素，则替换堆顶元素并调整堆。
- 最终，堆顶元素即为第 k 个最大的元素。

代码实现

import heapq

def findKthLargest(nums, k):
    min_heap = nums[:k]
    heapq.heapify(min_heap)
    for num in nums[k:]:
        if num > min_heap[0]:
            heapq.heappushpop(min_heap, num)
    return min_heap[0]

# 测试案例
print(findKthLargest([3,2,1,5,6,4], 2))  # 输出: 5
print(findKthLargest([3,2,3,1,2,4,5,5,6], 4))  # 输出: 4

复杂度分析

时间复杂度：
- 快速选择（Quickselect）：O(n)，平均情况下，每次划分会将数组分成两部分。
- 堆排序：O(n log k)，维护一个大小为 k 的最小堆。
空间复杂度：
- 快速选择（Quickselect）：O(1)，使用了常数个额外空间。
- 堆排序：O(k)，用于存储大小为 k 的最小堆。