一、问题描述:
给定整数数组 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
二、基于堆排序的选择方法:建立一个大根堆,堆顶元素nums[0]为最大值,做 k−1次删除操作后的堆顶元素就是数组中第 k 个最大的元素。
1、堆是什么?
堆是一种特殊的完全二叉树,具有堆化的特性,可以用数组实现。与一般的排序方式所定义的有序不同,看似堆数组中的数字并未按照升序 或 降序排列,但其实这棵树是有序的状态。按照元素升序和降序排序分为大根堆和小根堆。
大根堆: 父结点的值 大于或等于 其子结点的值。
小根堆: 父结点的值 小于或等于 其子结点的值。
与二叉树类似,堆能以 O(logN) 的时间复杂度完成插入、删除和查找操作,通过调整数组中元素的顺序,维护堆的结构。
2、构建大根堆
在最大堆中,每个节点的值都大于或等于其子节点的值。由于叶子节点没有子节点,它们已经满足了这个性质,因此不需要进行任何调整。而最后一个非叶子节点的索引是数组长度的一半减一。因此,从数组长度的一半 n / 2 向前遍历,可以确保每个非叶子节点都能被正确处理。
public void buildMaxHeap(int[] a, int n) {
//从数组长度的一半处向前遍历,可以确保每个非叶子节点都能被正确处理。
for(int i = n / 2; i >= 0; --i) {
maxHeapify(a, i, n);
}
}
3、调整大根堆
从最后一个非叶子节点开始向前遍历,比较自己与左右子结点的大小,如果小于子结点就交换(即:下调 )。下调之后继续与新的左右孩子结点进行比较,能够下调就下调,直到不能下调为止。向前继续移动,直到所有结点均遍历一遍,所有父结点均大于其孩子结点,便成为了一棵大根堆。
//和左右子节点比较,若大于子节点,向下调
public void maxHeapify(int[] a, int i, int n) {
int l = i * 2 + 1, r = i * 2 + 2, max = i;
if (l < n && a[l] > a[max]) {
max = l;
}
if (r < n && a[r] > a[max]) {
max = r;
}
if (max != i) {
swap(a, i, max);
maxHeapify(a, max, n);//递归调用,直到满足根节点大于左右节点的值
}
}
4、删除操作
我们要找到第K大的元素,那么需要从堆中删除K次最大元素nums[0]。每次将堆顶元素与最后一个元素进行交换,这样最大值就来到了数组的最后。由于堆顶发生了变化,可能不再是一个大根堆,因此需要对大根堆进行调整。
for(int i = nums.length - 1; i >= nums.length - k + 1; --i) {
swap(nums, 0, i);//堆顶元素与数组最后一位元素交换
--n;//长度减一
maxHeapify(nums, 0, n);//删除堆顶元素,无序的部分被放到末尾
}
5、完整代码:
class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
//数组中的第K个最大元素就是第n - k大的元素,对应排序后的数组的第n - k个元素
buildMaxHeap(nums, n);
for(int i = nums.length - 1; i >= nums.length - k + 1; --i) {
swap(nums, 0, i);//堆顶元素与数组最后一位元素交换
--n;//长度减一
maxHeapify(nums, 0, n);//删除堆顶元素,无序的部分被放到末尾
}
return nums[0];//删除K次,返回堆顶元素,即为我们要找的值
}
public void buildMaxHeap(int[] a, int n) {
//从数组长度的一半处向前遍历,可以确保每个非叶子节点都能被正确处理。
for(int i = n / 2; i >= 0; --i) {
maxHeapify(a, i, n);
}
}
//和左右子节点比较,若大于子节点,向下调
public void maxHeapify(int[] a, int i, int n) {
int l = i * 2 + 1, r = i * 2 + 2, max = i;
if (l < n && a[l] > a[max]) {
max = l;
}
if (r < n && a[r] > a[max]) {
max = r;
}
if (max != i) {
swap(a, i, max);
maxHeapify(a, max, n);//递归调用,直到满足根节点大于左右节点的值
}
}
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
- 时间复杂度分析:总体而言,这段代码使用了堆排序的思想,在构建最大堆后,通过反复交换堆顶元素和末尾元素,并对堆进行调整,最终得到第 k 个最大的元素。时间复杂度为 O(nlogn),空间复杂度为 O(1)。
三、基于快速排序的选择方法:先对原数组升序排序,再返回倒数第 k个位置。
快速排序是一种常用的排序算法,其基本思想是通过选取一个基准值,将数组分割成两部分,一部分小于基准值,另一部分大于基准值,然后对这两部分分别进行递归排序。具体步骤如下:
- 选择一个基准值(通常是数组的第一个元素)。
- 将数组中小于基准值的元素移到基准值的左边,大于基准值的元素移到基准值的右边。
- 继续对基准值左右两部分分别递归进行快速排序。
- 这是一个递归过程,直到每个子数组的大小为 1 或 0 时,排序完成。
代码示例:
class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
// 数组中的第 k 个最大元素就是第 n - k 大的元素,对应排序后的数组的第 n - k 个元素
return quickselect(nums, 0, n - 1, n - k);
}
// 快速选择算法
int quickselect(int[] nums, int l, int r, int k) {
// 如果左右指针相遇,说明排序完成
if (l == r) return nums[k];
// 以 nums[l] 为基准,将数组中小于基准值的元素移到基准值的左边,大于基准值的元素移到基准值的右边
int x = nums[l], i = l - 1, j = r + 1;
while (i < j) {
i++; while (nums[i] < x) i++; // 找到第一个大于等于基准值的元素
j--; while (nums[j] > x) j--; // 找到第一个小于等于基准值的元素
// 如果 i < j,交换这两个元素
if (i < j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
// 根据 j 的位置确定下一步递归的范围
if (k <= j) return quickselect(nums, l, j, k); // 第 k 个最大的元素在左边部分
else return quickselect(nums, j + 1, r, k); // 第 k 个最大的元素在右边部分
}
}
- 时间复杂度分析:这种方法的时间复杂度平均情况下为 O(n),最坏情况下为 O(n^2)。