Leetcode 215 数组中的第K个最大元素
Leetcode 215: 数组中的第K个最大元素 是一道非常经典的数组排序与查找问题，也是面试中非常常见的问题。考察重点包括：排序、堆排序、快速选择等多种方法，其中需要快速定位第K个最大元素。
问题描述
- 给定一个未排序的数组
nums，要求返回其中第k个最大的元素。 - 注意，第
k大的元素是按降序排列的第k个元素。
示例输入输出
输入: nums = [3,2,1,5,6,4], k = 2
输出: 5
输入: nums = [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
解法 1：排序
思路
- 最简单直接的方法是对数组进行排序，然后返回第
k大的元素。 - 将数组按降序排序，第
k大的元素就是索引为k-1的元素。
代码模板
import java.util.Arrays;
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums); // 默认是升序排列
return nums[nums.length - k]; // 倒数第 k 个就是第 k 大
}
}
复杂度分析
- 时间复杂度: O(n log n)
- 使用排序算法对数组排序，最小复杂度为 O(n log n)（如快速排序、归并排序）。
- 空间复杂度: O(1) （如果使用就地排序），或 O(n) （如果使用额外空间的排序算法）。
适用场景
- 当数据量较小（如 n < 1000）时可以快速实现，易于理解和写出。
- 面试时作为最基础的解法，可以先写出来确保正确性。
解法 2：堆排序 (使用最小堆)
思路
-
最小堆可以维护一个包含
k个元素的小顶堆，其中堆顶元素始终为当前堆中最小的元素。- 遍历数组。
- 对于当前元素：
- 如果堆大小小于
k，直接将元素加入堆。 - 如果堆已经满，并且当前元素大于堆顶元素，则将堆顶元素替换为当前元素，并调整堆。
- 如果堆大小小于
-
遍历完成后，堆顶元素就是第
k大的元素。
代码模板
import java.util.PriorityQueue;
class Solution {
public int findKthLargest(int[] nums, int k) {
// 初始化一个最小堆，容量为 k
PriorityQueue<Integer> heap = new PriorityQueue<>(k);
// 遍历数组
for (int num : nums) {
if (heap.size() < k) {
heap.offer(num); // 如果堆未满，直接加入
} else if (num > heap.peek()) {
heap.poll(); // 弹出最小值
heap.offer(num); // 加入当前元素
}
}
// 返回堆顶元素
return heap.peek();
}
}
复杂度分析
- 时间复杂度: O(n log k)
- 遍历数组需要 O(n)，每次堆的插入与删除操作需要 O(log k)。
- 空间复杂度: O(k)
- 堆中只存储
k个元素。
- 堆中只存储
适用场景
- 数据量较大，但 k 值较小，适合用堆来优化。
- 中等规模数据场景的高效解决方案。
解法 3：快速选择 (Quickselect)
思路
-
快速选择是快速排序的变种，只关注目标元素所在的部分，不需要对整个数组完全排序。
- 随机选择一个枢轴 (pivot)；
- 将数组分区，使 pivot 左侧的元素都小于 pivot，右侧的元素都大于 pivot；
- 判断 pivot 的位置：
- 如果 pivot 恰好是第
n-k大元素，则直接返回； - 如果 pivot 在第
n-k的右侧，则在左半部分递归； - 如果 pivot 在第
n-k的左侧，则在右半部分递归。
- 如果 pivot 恰好是第
-
递归实现快速选择。
代码模板
import java.util.Random;
class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
return quickSelect(nums, 0, n - 1, n - k);
}
private int quickSelect(int[] nums, int left, int right, int index) {
// 分区操作
int pivot = partition(nums, left, right);
if (pivot == index) {
return nums[pivot]; // 找到结果
} else if (pivot < index) {
return quickSelect(nums, pivot + 1, right, index);
} else {
return quickSelect(nums, left, pivot - 1, index);
}
}
private int partition(int[] nums, int left, int right) {
int pivot = nums[right]; // 选择最右侧元素为枢轴
int i = left - 1; // i 指向比 pivot 小的区域的最后一个元素
for (int j = left; j < right; j++) {
if (nums[j] <= pivot) { // 把小于等于 pivot 的元素交换到左侧
i++;
swap(nums, i, j);
}
}
swap(nums, i + 1, right);
return i + 1; // 返回 pivot 的最终位置
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
复杂度分析
- 平均时间复杂度: O(n)
- 快速选择对每次迭代部分划分，平均情况下不断减少搜索范围。
- 最坏时间复杂度: O(n²)
- 在极端情况下（如总是选择不平衡的 pivot），时间复杂度退化为 O(n²)。
- 空间复杂度: O(1)
- 原地分区，不占用额外空间。
适用场景
- 当需要更高效的数据操作，而数据量较大时，非常适合快速选择。
- 均值场景下效率优于排序和堆。
解法 4：使用内置库
思路
- 使用 Java 的内置库，如
Arrays.sort或PriorityQueue，快速获取目标元素。
代码模板
import java.util.Collections;
import java.util.PriorityQueue;
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int num : nums) {
maxHeap.add(num);
}
for (int i = 1; i < k; i++) {
maxHeap.poll();
}
return maxHeap.poll();
}
}
快速 AC 策略
-
首选快速选择 (Quickselect, 解法 3)：
- 平均时间复杂度 O(n)，适合处理大规模数据。
- 适合面试或比赛中优先编写，凸显算法能力。
-
堆排序 (解法 2)：
- O(n log k) 的效率，适合
k较小的场景。 - 实现简单，非常稳定。
- O(n log k) 的效率，适合
-
排序 (解法 1)：
- 简单易实现，适合快速验证结果或小规模数据。
根据场景选择合适解法，可以快速 AC 本题！