题目描述
给定整数数组 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 提示： 1 <= k <= nums.length <= 105 -104 <= nums[i] <= 104
原题：LeetCode 215
思路及实现
方式一：快速选择排序
思路
快速选择算法是快速排序的一个变种，用于在未排序的列表中找到第 k 小（或第 k 大）的元素。该算法的核心思想是利用快速排序的分区过程来定位目标元素。在分区过程中，我们选择一个枢轴（pivot）元素，并将数组划分为两部分：一部分包含比枢轴小的元素，另一部分包含比枢轴大的元素。如果枢轴的位置正好是我们想要找的 k 的位置，那么算法结束；如果枢轴的位置在 k 的左侧，那么目标元素必定在枢轴的右侧；反之亦然。
代码实现
Java版本
public class Solution { /** * 找到数组中第k大的元素 * * @param nums 待搜索的数组 * @param k 要查找的是第k大的元素 * @return 返回第k大的元素 */ public int findKthLargest(int[] nums, int k) { int n = nums.length; // 数组长度 int targetIndex = n - k; // 要找的是第k大的元素，在排序后的数组中对应的索引位置 return quickSelect(nums, 0, n - 1, targetIndex); // 调用快速选择算法查找目标元素 } /** * 快速选择算法的核心实现 * * @param nums 待搜索的数组 * @param left 搜索区间的左边界 * @param right 搜索区间的右边界 * @param targetIndex 目标元素在排序后数组中的索引位置 * @return 返回目标元素的值 */ private int quickSelect(int[] nums, int left, int right, int targetIndex) { if (left == right) { // 如果左右指针相等，说明区间内只有一个元素，直接返回该元素 return nums[left]; } // 调用分区操作，返回枢轴元素的索引位置 int pivotIndex = partition(nums, left, right); if (pivotIndex == targetIndex) { // 如果枢轴位置恰好等于目标位置，直接返回枢轴元素 return nums[pivotIndex]; } else if (pivotIndex < targetIndex) { // 如果枢轴位置小于目标位置，说明目标元素在枢轴右侧，继续搜索右侧区间 return quickSelect(nums, pivotIndex + 1, right, targetIndex); } else { // 如果枢轴位置大于目标位置，说明目标元素在枢轴左侧，继续搜索左侧区间 return quickSelect(nums, left, pivotIndex - 1, targetIndex); } } /** * 数组分区操作，选取枢轴元素，将小于枢轴的元素移动到左侧，大于枢轴的元素移动到右侧 * * @param nums 待分区的数组 * @param left 分区的左边界 * @param right 分区的右边界 * @return 返回枢轴元素的索引位置 */ private int partition(int[] nums, int left, int right) { int pivot = nums[right]; // 选取最右边的元素作为枢轴 int i = left; // 初始化左侧指针 for (int j = left; j < right; j++) { // 将小于枢轴的元素移动到左侧 if (nums[j] <= pivot) { swap(nums, i, j); // 交换元素 i++; // 左指针右移 } } swap(nums, i, right); // 将枢轴移动到正确的位置 return i; // 返回枢轴元素的索引位置 } /** * 交换数组中两个元素的位置 * * @param nums 数组 * @param i 第一个元素的索引 * @param j 第二个元素的索引 */ private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } •
说明：
该代码首先定义了一个 findKthLargest 方法，它接受一个整数数组 nums 和一个整数 k 作为输入，返回第 k 大的元素。该方法使用快速选择算法来定位目标元素。在 partition 方法中，我们随机选择一个枢轴元素，并对数组进行分区。swap 方法用于交换数组中两个元素的位置。
C语言版本
#include <stdio.h> /** * @brief 数组分区操作 * * 将数组 nums 中小于等于枢轴的元素移动到左侧，大于枢轴的元素移动到右侧。 * * @param nums 待分区的数组 * @param left 分区的左边界 * @param right 分区的右边界 * @return 返回枢轴元素的索引位置 */ int partition(int* nums, int left, int right) { int pivot = nums[right]; // 选取最右边的元素作为枢轴 int i = left; // 初始化左侧指针 for (int j = left; j < right; j++) { // 将小于等于枢轴的元素移动到左侧 if (nums[j] <= pivot) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; i++; // 左指针右移 } } int temp = nums[i]; nums[i] = nums[right]; nums[right] = temp; // 将枢轴移动到正确的位置 return i; // 返回枢轴元素的索引位置 } /** * @brief 快速选择算法的核心实现 * * 查找数组中第 targetIndex 大的元素。 * * @param nums 待搜索的数组 * @param left 搜索区间的左边界 * @param right 搜索区间的右边界 * @param targetIndex 目标元素在排序后数组中的索引位置 * @return 返回目标元素的值 */ int quickSelect(int* nums, int left, int right, int targetIndex) { if (left == right) { // 如果左右指针相等，说明区间内只有一个元素，直接返回该元素 return nums[left]; } // 调用分区操作，返回枢轴元素的索引位置 int pivotIndex = partition(nums, left, right); if (pivotIndex == targetIndex) { // 如果枢轴位置恰好等于目标位置，直接返回枢轴元素 return nums[pivotIndex]; } else if (pivotIndex < targetIndex) { // 如果枢轴位置小于目标位置，说明目标元素在枢轴右侧，继续搜索右侧区间 return quickSelect(nums, pivotIndex + 1, right, targetIndex); } else { // 如果枢轴位置大于目标位置，说明目标元素在枢轴左侧，继续搜索左侧区间 return quickSelect(nums, left, pivotIndex - 1, targetIndex); } } /** * @brief 查找数组中第k大的元素 * * @param nums 待搜索的数组 * @param numsSize 数组的长度 * @param k 要查找的是第k大的元素 * @return 返回第k大的元素 */ int findKthLargest(int* nums, int numsSize, int k) { int targetIndex = numsSize - k; // 要找的是第k大的元素，在排序后的数组中对应的索引位置 return quickSelect(nums, 0, numsSize - 1, targetIndex); // 调用快速选择算法查找目标元素 } /** * @brief 主函数 * * 执行查找数组中第k大的元素的操作，并输出结果。 * * @return 0 表示程序正常退出 */ int main() { int nums[] = {3, 2, 1, 5, 6, 4}; // 待搜索的数组 int k = 2; // 要查找的是第2大的元素 int n = sizeof(nums) / sizeof(nums[0]); // 数组的长度 int result = findKthLargest(nums, n, k); // 调用函数查找第k大的元素 printf("The %dth largest element is: %d\n", k, result); // 输出结果 return 0; // 程序正常退出 }
说明：
main函数作为程序的入口点，包含了测试代码，用于验证快速选择算法的正确性。
Python3版本
def findKthLargest(nums, k): # 要找的是第k大的元素，相当于在排序后的数组中找倒数第k个元素 target_index = len(nums) - k # 使用快速选择算法查找目标元素 return quick_select(nums, 0, len(nums) - 1, target_index) # 快速选择算法实现 def quick_select(nums, left, right, target_index): if left == right: # 如果左右指针相等，则直接返回该位置的元素 return nums[left] # 选取枢轴 pivot_index = partition(nums, left, right) if pivot_index == target_index: # 如果枢轴位置恰好等于目标位置，直接返回枢轴元素 return nums[pivot_index] elif pivot_index < target_index: # 如果枢轴位置小于目标位置，说明目标元素在枢轴右侧，继续搜索右侧区间 return quick_select(nums, pivot_index + 1, right, target_index) else: # 如果枢轴位置大于目标位置，说明目标元素在枢轴左侧，继续搜索左侧区间 return quick_select(nums, left, pivot_index - 1, target_index) # 数组分区操作 def partition(nums, left, right): # 选取最右边的元素作为枢轴 pivot = nums[right] pivot_index = left for i in range(left, right): # 将小于枢轴的元素移动到左侧 if nums[i] <= pivot: nums[pivot_index], nums[i] = nums[i], nums[pivot_index] pivot_index += 1 # 将枢轴移动到正确位置 nums[pivot_index], nums[right] = nums[right], nums[pivot_index] return pivot_index
说明：
快速选择（QuickSelect）算法，用于在未排序的数组中找到第target_index小的元素。快速选择算法是快速排序算法的一个变种，用于解决未排序数组中的第k小（或大）元素问题。
通过递归地分区数组，并在每个分区中查找目标元素，从而高效地找到第target_index小的元素。由于快速选择算法的平均时间复杂度为O(n)，其中n是数组的长度，因此它在处理大型数据集时非常有效
复杂度分析
- 时间复杂度：在平均情况下，快速选择算法的时间复杂度为O(n)，其中n为数组的元素个数。最坏情况下的时间复杂度为O(n^2)，但平均情况下仍然是O(n)。
- 空间复杂度：快速选择算法的空间复杂度主要取决于递归调用的栈空间。最坏情况下的空间复杂度为O(n)，但平均情况下为O(logn)。
快速选择算法是一种高效的解决方案，能够在无序数组中快速地找到第k个最大或最小元素。它具有较低的平均时间复杂度和较小的平均空间复杂度。
方式二：最小堆（最小优先队列）
思路
使用一个最小堆（最小优先队列）来维护当前最大的 k 个元素。遍历数组，对于每个元素，如果堆的大小小于 k，则直接将其加入堆中；如果堆的大小等于 k，则比较当前元素与堆顶元素的大小，如果当前元素更大，则弹出堆顶元素，将当前元素加入堆中。最后堆顶元素即为第 k 个最大的元素。
代码实现
Java版本
import java.util.PriorityQueue; class Solution { public int findKthLargest(int[] nums, int k) { // 创建最小堆 PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 初始化堆 for (int i = 0; i < k; i++) { minHeap.offer(nums[i]); } // 维持堆的大小为k for (int i = k; i < nums.length; i++) { if (nums[i] > minHeap.peek()) { minHeap.poll(); minHeap.offer(nums[i]); } } // 返回第k大的元素 return minHeap.peek(); } }
说明：
虽然代码使用最小堆来解决问题，但返回的是第k大的元素，因为堆中始终保存着最大的k个元素，且堆顶是最小的那个。如果需要找第k小的元素，则无需任何修改；但如果要找第k大的元素，并希望代码更加直观，可以考虑使用最大堆或者对数组进行降序排序后再使用最小堆。
C语言版本
#include<stdlib.h> int findKthLargest(int* nums, int numsSize, int k) { // 创建最小堆 int* minHeap = (int*)malloc(sizeof(int) * k); int i; // 初始化堆 for (i = 0; i < k; i++) { minHeap[i] = nums[i]; } buildMinHeap(minHeap, k); // 维持堆的大小为k for (i = k; i < numsSize; i++) { if (nums[i] > minHeap[0]) { minHeap[0] = nums[i]; heapify(minHeap, k, 0); } } // 返回第k大的元素 int result = minHeap[0]; free(minHeap); return result; } void buildMinHeap(int* array, int size) { int i; for (i = (size - 2) / 2; i >= 0; i--) { heapify(array, size, i); } } void heapify(int* array, int size, int index) { int left = 2 * index + 1; int right = 2 * index + 2; int smallest = index; if (left < size && array[left] < array[smallest]) { smallest = left; } if (right < size && array[right] < array[smallest]) { smallest = right; } if (smallest != index) { swap(&array[index], &array[smallest]); heapify(array, size, smallest); } } void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } •
说明
代码首先创建一个大小为k的最小堆，并使用数组的前k个元素初始化它。然后，它遍历数组的剩余部分，每次遇到比堆顶元素大的元素时，就替换堆顶元素并重新调整堆。最后，返回堆顶元素，即第k大的元素。这种方法的时间复杂度是O(n log k)，其中n是数组的大小。
Python3版本
import heapq # 导入heapq模块，用于操作堆 class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: # 创建一个空的最小堆 minHeap = [] # 初始化堆 # 将数组的前k个元素添加到最小堆中 for i in range(k): heapq.heappush(minHeap, nums[i]) # 遍历数组的剩余部分 # 维持堆的大小为k，确保堆顶元素始终是堆中最小的元素 for i in range(k, len(nums)): # 如果当前元素大于堆顶元素，那么弹出堆顶元素，并将当前元素压入堆中 # 这样，堆顶元素始终是遍历过的元素中第k大的元素 if nums[i] > minHeap[0]: heapq.heappop(minHeap) heapq.heappush(minHeap, nums[i]) # 最后，堆顶元素就是第k大的元素 # 因为堆的大小始终为k，所以堆顶元素就是遍历过的k个最大元素中最小的那个，即第k大的元素 return minHeap[0]
说明：
导入heapq模块，这是Python标准库中的一个模块，用于实现堆队列算法。
虽然这段代码使用了一个最小堆来解决问题，但返回的实际上是第k大的元素，因为堆中始终保存着最大的k个元素，而堆顶是最小的那个。这意味着，如果我们需要找到第k小的元素，则这段代码可以直接使用。如果要找第k大的元素，则需要将数组逆序或者调整k的值（即使用len(nums) - k + 1作为目标位置）
复杂度分析
- 时间复杂度： 建立初始堆的时间复杂度为O(k * logk)，维护堆的大小为k的时间复杂度为O((n - k) * logk)，总时间复杂度为O(n * logk)。
- 空间复杂度： 最小堆所使用的空间为O(k)。
总结
| 最小堆 | 快速选择算法 | |
| 优点 | - 简单易实现 | - 高效，能找到第k个最大或最小元素 |
| - 适用于动态数据流 | - 原地操作，不需要额外空间 | |
| 缺点 | - 空间复杂度较高 | - 平均情况下较高时间复杂度 |
| 时间复杂度 | - 平均：O(nlogk) | - 平均：O(n) |
| - 最差：O(nlogk) | - 最差：O(n^2) | |
| 空间复杂度 | - O(k) | - 平均：O(logn) |
| - 最差：O(n) | ||
| 其他 | - 用于处理动态数据流 | - 快速选择是快速排序的关键步骤 |
最小堆的优点在于实现简单，适用于动态数据流，但其空间复杂度较高，需要额外的空间来存储堆。
快速选择算法的优点在于高效，能够快速找到第k个最大或最小元素，并且是原地操作，不需要额外空间。快速选择是快速排序算法的关键步骤之一，利用分治思想进行划分并维护子区间的方式进行快速查找。
最小堆的时间复杂度是平均和最差情况下都是O(nlogk)，空间复杂度为O(k)。
快速选择算法的时间复杂度是平均情况下为O(n)，最差情况下为O(n^2)（当数组完全有序时），空间复杂度为平均情况下O(logn)，最差情况下为O(n)。
综上所述，最小堆适用于处理动态数据流，实现简单但空间复杂度较高；而快速选择算法在平均情况下具有较低的时间复杂度和较小的空间复杂度，但最差情况下时间复杂度较高。因此，根据情况选择合适的算法来解决特定的问题。
相似题目
以上是一些与LeetCode 215题相似的题目，它们都涉及到在数组、数据流或矩阵中查找第K个最大或最小元素的问题。它们的难度不同，有简单和中等难度的题目
