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：堆排序 (使用最小堆)

思路

1. 最小堆可以维护一个包含 k 个元素的小顶堆，其中堆顶元素始终为当前堆中最小的元素。

   • 遍历数组。
   • 对于当前元素：
     • 如果堆大小小于 k，直接将元素加入堆。
     • 如果堆已经满，并且当前元素大于堆顶元素，则将堆顶元素替换为当前元素，并调整堆。

2. 遍历完成后，堆顶元素就是第 k 大的元素。

---

代码模板

import java.util.PriorityQueue;class Solution {public int findKthLargest(int[] nums, int k) {// 初始化一个最小堆，容量为 kPriorityQueue<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)

思路

1. 快速选择是快速排序的变种，只关注目标元素所在的部分，不需要对整个数组完全排序。

   • 随机选择一个枢轴 (pivot)；
   • 将数组分区，使 pivot 左侧的元素都小于 pivot，右侧的元素都大于 pivot；
   • 判断 pivot 的位置：
     • 如果 pivot 恰好是第 n-k 大元素，则直接返回；
     • 如果 pivot 在第 n-k 的右侧，则在左半部分递归；
     • 如果 pivot 在第 n-k 的左侧，则在右半部分递归。

2. 递归实现快速选择。

---

代码模板

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 策略

1. 首选快速选择 (Quickselect, 解法 3)：

   • 平均时间复杂度 O(n)，适合处理大规模数据。
   • 适合面试或比赛中优先编写，凸显算法能力。

2. 堆排序 (解法 2)：

   • O(n log k) 的效率，适合 k 较小的场景。
   • 实现简单，非常稳定。

3. 排序 (解法 1)：

   • 简单易实现，适合快速验证结果或小规模数据。

根据场景选择合适解法，可以快速 AC 本题！