LeetCode题练习与总结：数组中的第K个最大元素--215

本文主要是介绍LeetCode题练习与总结：数组中的第K个最大元素--215，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目描述

给定整数数组 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 <= 10^5
-10^4 <= nums[i] <= 10^4

二、解题思路

理解问题：给定一个整数数组 nums 和一个整数 k，要求返回数组中第 k 个最大的元素。这里的第 k 个最大元素是指在数组排序后，从大到小数第 k 个元素。
选择算法：为了在 O(n) 的时间复杂度内找到第 k 个最大的元素，我们可以使用快速选择算法（Quickselect）。这个算法是快速排序的变种，但不需要对整个数组进行排序，它通过分区的思想来找到第 k 大的元素。
快速选择算法步骤：
- 从数组中选择一个基准元素（pivot）。
- 将数组划分为两部分：一部分包含所有大于或等于基准元素的元素，另一部分包含所有小于基准元素的元素。
- 确定基准元素在数组中的位置。
- 如果基准元素的位置正好是 k-1，则找到了第 k 个最大的元素。
- 如果基准元素的位置大于 k-1，则第 k 个最大的元素在基准元素的左侧，递归地在左侧子数组中查找。
- 如果基准元素的位置小于 k-1，则第 k 个最大的元素在基准元素的右侧，递归地在右侧子数组中查找。
代码实现：
- findKthLargest 方法是主方法，调用 quickSelect 来找到第 k 个最大的元素。
- quickSelect 方法递归地找到第 k 个最大的元素。
- partition 方法用于对数组进行分区，将大于或等于基准元素的元素放在基准元素的左侧，将小于基准元素的元素放在右侧。
- swap 方法用于交换数组中的两个元素。

以下是具体的解题步骤：

初始化 left 为 0，right 为 nums.length - 1。
在 quickSelect 方法中，通过 partition 方法找到一个基准元素的位置 pivotIndex。
比较 pivotIndex 和 k-1：
- 如果相等，返回 nums[pivotIndex]。
- 如果 pivotIndex 大于 k-1，则在左侧子数组 [left, pivotIndex - 1] 中递归调用 quickSelect。
- 如果 pivotIndex 小于 k-1，则在右侧子数组 [pivotIndex + 1, right] 中递归调用 quickSelect。

通过这种方式，我们可以在平均 O(n) 的时间复杂度内找到第 k 个最大的元素。

三、具体代码

class Solution {public int findKthLargest(int[] nums, int k) {return quickSelect(nums, 0, nums.length - 1, k);}private int quickSelect(int[] nums, int left, int right, int k) {int pivotIndex = partition(nums, left, right);// 因为我们要找的是第 k 个最大的元素，所以 k 应该是相对于排序后的数组的位置if (pivotIndex == k - 1) {return nums[pivotIndex];} else if (pivotIndex > k - 1) {// 如果 pivotIndex 大于 k - 1，说明第 k 个最大的元素在左侧return quickSelect(nums, left, pivotIndex - 1, k);} else {// 如果 pivotIndex 小于 k - 1，说明第 k 个最大的元素在右侧return quickSelect(nums, pivotIndex + 1, right, k);}}private int partition(int[] nums, int left, int right) {int pivot = nums[right];int i = left;for (int j = left; j < right; j++) {// 我们希望比 pivot 大的数在左边，因此这里应该是 >=if (nums[j] >= pivot) {swap(nums, i, j);i++;}}swap(nums, i, right);return i;}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

快速选择算法（Quickselect）的平均时间复杂度是 O(n)，但最坏情况下是 O(n^2)。以下是详细的解释：

平均情况：在平均情况下，每次调用 partition 方法都会将数组分成两个大致相等的部分。这意味着每次递归调用处理的数组大小大约减半。因此，算法的运行时间大致遵循一个几何级数，其总和是 O(n)。具体来说，时间复杂度是 T(n) = T(n/2) + O(n)，解这个递归方程得到平均时间复杂度为 O(n)。
最坏情况：在最坏情况下，每次分区操作选择的基准元素都是最小或最大的元素，导致每次递归只减少一个元素。这种情况下，算法的运行时间遵循一个线性递归，其时间复杂度为 O(n^2)。例如，如果数组已经排序，每次分区操作只减少一个元素。

2. 空间复杂度

快速选择算法的空间复杂度是 O(1)，也就是常数空间。以下是详细的解释：

递归栈空间：尽管算法是递归的，但每次递归调用只使用常数额外空间（不包括输入数组）。在最坏情况下，递归的深度可以达到 n，这意味着递归栈空间是 O(n)。然而，由于问题要求返回第 k 个最大的元素，实际上递归的深度不会超过 n，因此递归栈空间仍然是 O(n)。
额外空间：除了递归栈空间之外，算法在执行过程中只使用了常数额外空间。例如，partition 方法中使用的变量 pivot、i、j 和 temp 都是固定数量的变量，与输入数组的大小无关。

需要注意的是，尽管递归栈空间在最坏情况下是 O(n)，但通常我们在分析空间复杂度时，如果不特别指明，是指除了输入数据之外所需的空间，因此在这个意义上，算法的空间复杂度是 O(1)。

五、总结知识点

快速选择算法（Quickselect）：
- 快速选择算法是基于快速排序的选择算法，用于在未排序的数组中找到第 k 个最大（或最小）的元素。
- 它是分而治之策略的一个实例，具有与快速排序相似的递归结构。
递归（Recursion）：
- quickSelect 方法是一个递归方法，它通过不断缩小搜索范围来找到所需的元素。
- 递归的基本条件是当 pivotIndex 等于 k - 1 时，表示找到了第 k 个最大的元素。
分治法（Divide and Conquer）：
- 快速选择算法使用了分治法的思想，将大问题分解成小问题来解决。
分区（Partitioning）：
- partition 方法用于将数组分为两部分，一部分包含所有大于或等于基准值的元素，另一部分包含所有小于基准值的元素。
基准元素（Pivot）的选择：
- 在这个实现中，基准元素被选为数组的最后一个元素。
交换（Swapping）：
- swap 方法用于交换数组中的两个元素。
数组操作：
- 代码涉及数组的遍历和元素的比较。
整数（Integer）操作：
- 代码中使用了整数类型进行数组索引和比较操作。
算法设计：
- 快速选择算法的设计是高效算法设计的一个例子，它利用了快速排序的分区思想，但不需要对整个数组进行排序。
递归栈（Recursive Stack）：
- 递归方法会使用系统栈来存储每次递归调用的状态，包括局部变量和返回地址。
边界条件检查：
- 在 quickSelect 方法中，通过比较 pivotIndex 和 k - 1 来确定递归的边界条件。