算法题：数组中的第 K 个最大元素（中等难度）

一、题目

给定整数数组 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 <= 104
• -104 <= nums[i] <= 104

二、解法

1、直接排序，把重复的值过滤掉，放在一个数组里，然后取第二大的值，简单粗暴

def quick_sort(arr):#快速排序if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)def sort_and_deduplicate(nums):# 使用 set 去重unique_nums = list(set(nums))# 对去重后的数组进行排序return quick_sort(unique_nums)# 示例
nums = [3, 2, 1, 3, 5, 6, 4, 2, 5]
sorted_unique_nums = sort_and_deduplicate(nums)
print(sorted_unique_nums)  # 输出：[1, 2, 3, 4, 5, 6]

2、利用堆

def findKthLargest(nums, k):min_heap = [] #用来表示一个最小堆，堆通常通过列表实现for num in nums:if len(min_heap) < k:  # 检查堆的大小是否小于 kheapq.heappush(min_heap, num)else:if num > min_heap[0]:  # 如果堆的大小已经等于 kheapq.heapreplace(min_heap, num)return min_heap[0]  # 堆顶元素是第 K 大的元素

三、堆相关的知识科普

关于堆知识的总结：

关于堆知识的总结

• 堆是一种特殊的完全二叉树，满足堆序性质。

• 最小堆的堆顶是最小值，最大堆的堆顶是最大值。

• 堆的主要操作包括插入、弹出堆顶元素和堆化。

• 堆在优先队列、堆排序、查找第 K 大/小的元素等场景中非常有用。

• 在 Python 中，堆通过 heapq 模块实现，默认支持最小堆。

1. 堆的定义

堆是一种特殊的完全二叉树，满足以下两个条件：

1. 完全二叉树：

   • 堆是一棵完全二叉树，即每一层（除了最后一层）都被完全填满，并且所有节点都尽可能向左对齐。

   • 这种结构使得堆可以用数组（列表）高效地表示，而不需要使用指针。

2. 堆序性质：

   • 堆中的每个节点都满足某种顺序关系，具体取决于堆的类型：

     • 最小堆（Min-Heap）：每个节点的值都小于或等于其子节点的值。

     • 最大堆（Max-Heap）：每个节点的值都大于或等于其子节点的值。

2. 堆的类型

堆主要有两种类型：

1. 最小堆（Min-Heap）：

   • 堆顶（根节点）是堆中最小的元素。

   • 适用于需要快速访问最小值的场景，如优先队列。

2. 最大堆（Max-Heap）：

   • 堆顶（根节点）是堆中最大的元素。

   • 适用于需要快速访问最大值的场景，如任务调度。

3. 堆的结构

堆通常用数组（列表）来表示，因为完全二叉树的结构使得数组可以高效地映射树的节点。对于一个数组 heap：

• 索引 i 的节点：

  • 左子节点的索引是 2 * i + 1

  • 右子节点的索引是 2 * i + 2

  • 父节点的索引是 (i - 1) // 2

示例：最小堆 假设有一个最小堆 [1, 3, 2, 6, 5, 4]，其结构如下：                                        

        1/   \3     2/ \   /6   5 4

4. 堆的操作

堆的主要操作包括：

1. 插入元素：

   • 将新元素添加到堆的末尾。

   • 通过“上浮”操作调整堆的结构，确保父节点小于（最小堆）或大于（最大堆）子节点。

2. 弹出堆顶元素：

   • 移除并返回堆顶元素（最小堆的最小值或最大堆的最大值）。

   • 将最后一个元素移到堆顶。

   • 通过“下沉”操作调整堆的结构，确保父节点小于（最小堆）或大于（最大堆）子节点。

3. 替换堆顶元素：

   • 弹出堆顶元素，并将新元素插入堆中，同时保持堆的大小不变。

   • 这是“上浮”和“下沉”操作的结合。

4. 堆化：

   • 将一个无序数组转换为一个有效的堆。

   • 在 Python 中，使用 heapq.heapify() 实现。

6. 堆的应用

堆在算法和数据结构中有着广泛的应用，包括但不限于：

1. 优先队列：

   • 最小堆用于实现最小优先队列。

   • 最大堆用于实现最大优先队列。

2. 堆排序：

   • 利用堆的性质对数组进行排序，时间复杂度为 O(n log n)。

3. 查找第 K 大/小的元素：

   • 使用最小堆或最大堆可以高效地找到数组中的第 K 大或第 K 小的元素。

4. 中位数查找：

   • 使用一个最大堆和一个最小堆可以动态维护数据流的中位数。

5. 合并有序数组：

   • 使用最小堆可以高效地合并多个有序数组。

7. Python 中的堆实现

Python 的 heapq 模块提供了对最小堆的支持。以下是一些常用操作：

Python复制

import heapq# 创建一个空堆
min_heap = []# 将一个列表转换为堆
nums = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(nums)# 向堆中添加元素
heapq.heappush(min_heap, 10)# 弹出堆顶元素
smallest = heapq.heappop(min_heap)# 替换堆顶元素
heapq.heapreplace(min_heap, 11)