10、数组中的第k个最大元素
题意
给定整数数组 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
解法及思路
方法一:返回升序排序以后索引为 len - k 的元素
题目已经告诉你了:
你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
因此,升序排序以后,返回索引为 len - k 这个元素即可。
这是最简单的思路,如果只答这个方法,可能面试官并不会满意,但是在我们平时的开发工作中,还是不能忽视这种思路简单的方法,我认为理由如下:
- 最简单同时也一定是最容易编码的,编码成功的几率最高,可以用这个最简单思路编码的结果和其它思路编码的结果进行比对,验证高级算法的正确性;
- 在数据规模小、对时间复杂度、空间复杂度要求不高的时候,真没必要上 “高大上” 的算法;
- 思路简单的算法考虑清楚了,有些时候能为实现高级算法铺路。这道题正是如此,“数组排序后的第 k 个最大的元素” ,语义是从右边往左边数第 k 个元素(从 1 开始),那么从左向右数是第几个呢,我们列出几个找找规律就好了。
一共 6 个元素,找第 2 大,索引是 4;6 个元素,找第 4 大,索引是 2。
因此,目标元素的索引是 len - k,即找最终排定以后位于 len - k 的那个元素;
- 低级算法往往容错性最好,即在输入不满足题目条件的时候,往往还能得到正确的答案,而高级算法对输入数据的要求就非常苛刻。
参考代码
import java.util.Arrays;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
Arrays.sort(nums);
return nums[len - k];
}
}
复杂度分析
时间复杂度:O(NlogN)。这里 N 是数组的长度,算法的性能消耗主要在排序,JDK 默认使用快速排序,因此时间复杂度为O(NlogN)。
空间复杂度:O(1)。这里是原地排序,没有借助额外的辅助空间。
到这里,已经分析出了:
- 应该返回最终排定以后位于 len - k 的那个元素;
学习过 “快速排序” 的朋友,一定知道一个操作叫 partition,它是 “分而治之” 思想当中 “分” 的那一步。
经过 partition 操作以后,每一次都能排定一个元素,并且这个元素左边的数都不大于它,这个元素右边的数都不小于它,并且我们还能知道排定以后的元素的索引。
于是可以应用 “减而治之”(分治思想的特例)的思想,把问题规模转化到一个更小的范围里。
于是得到方法二。
方法二:借助 partition 操作定位
方法二则是借助 partition 操作定位到最终排定以后索引为 len - k 的那个元素。
以下的描述基于 “快速排序” 算法知识的学习,如果忘记的朋友们可以翻一翻自己的《数据结构与算法》教材,复习一下,partition 过程、分治思想和 “快速排序” 算法的优化。
在学习 “快速排序” 的时候,接触的第 1 个操作就是 partition(切分),可以先复习一下
partition(切分)操作简单介绍如下:
- 对于某个索引 j,nums[j] 已经排定,即 nums[j] 经过 partition(切分)操作以后会放置在它 “最终应该放置的地方”;
- nums[left] 到 nums[j - 1] 中的所有元素都不大于 nums[j];
- nums[j + 1] 到 nums[right] 中的所有元素都不小于 nums[j]。
partition(切分)操作总能排定一个元素,还能够知道这个元素它最终所在的位置,这样每经过一次 partition操作就能缩小搜索的范围,这样的思想叫做 “减而治之”(是 “分而治之” 思想的特例)。
切分过程可以不借助额外的数组空间,仅通过交换数组元素实现。下面是参考代码:
参考代码
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
int left = 0;
int right = len - 1;
// 转换一下,第 k 大元素的索引是 len - k
int target = len - k;
while (true) {
int index = partition(nums, left, right);
if (index == target) {
return nums[index];
} else if (index < target) {
left = index + 1;
} else {
right = index - 1;
}
}
}
public static int partition(int[] array, int low, int high) {
// 取最后一个元素作为中心元素
int pivot = array[high];
// 定义指向比中心元素大的指针,首先指向第一个元素
int pointer = low;
// 遍历数组中的所有元素,将比中心元素大的放在右边,比中心元素小的放在左边
for (int i = low; i < high; i++) {
if (array[i] <= pivot) {
// 将比中心元素小的元素和指针指向的元素交换位置
// 如果第一个元素比中心元素小,这里就是自己和自己交换位置,指针和索引都向下一位移动
// 如果元素比中心元素大,索引向下移动,指针指向这个较大的元素,直到找到比中心元素小的元素,并交换位置,指针向下移动
swap(array, i, pointer);
pointer++;
}
}
// 将中心元素和指针指向的元素交换位置
swap(array, pointer, high);
return pointer;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
复杂度分析
时间复杂度:O(N)。这里 N 是数组的长度。
空间复杂度:O(1)。这里是原地排序,没有借助额外的辅助空间。
方法三:优先队列
优先队列的写法就很多了,这里例举一下所有能想到的。
假设数组有 len
个元素。
思路 1 :把 len
个元素都放入一个最小堆中,然后再 pop() 出 len - k 个元素,此时最小堆只剩下 k
个元素,堆顶元素就是数组中的第 k
个最大元素。
思路 2 :把 len
个元素都放入一个最大堆中,然后再 pop() 出 k - 1 个元素,因为前 k - 1 大的元素都被弹出了,此时最大堆的堆顶元素就是数组中的第 k
个最大元素。
思路 3 :只用 k
个容量的优先队列,而不用全部 len
个容量。
思路 4:用 k + 1
个容量的优先队列,使得上面的过程更“连贯”一些,到了 k
个以后的元素,就进来一个,出去一个,让优先队列自己去维护大小关系。
思路 5:综合考虑以上两种情况,总之都是为了节约空间复杂度。即 k
较小的时候使用最小堆,k
较大的时候使用最大堆。
根据以上思路,分别写出下面的代码:
思路 1 参考代码
//思路 1 :把 `len` 个元素都放入一个最小堆中,然后再 pop() 出 len - k 个元素,此时最小堆只剩下 `k` 个元素,堆顶元素就是数组中的第 `k` 个最大元素。
import java.util.PriorityQueue;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
// 使用一个含有 len 个元素的最小堆,默认是最小堆,可以不写 lambda 表达式:(a, b) -> a - b
PriorityQueue<Integer> minHeap = new PriorityQueue<>(len, (a, b) -> a - b);
for (int i = 0; i < len; i++) {
minHeap.add(nums[i]);
}
for (int i = 0; i < len - k; i++) {
minHeap.poll();
}
return minHeap.peek();
}
}
思路 2 参考代码
//思路 2 :把 `len` 个元素都放入一个最大堆中,然后再 pop() 出 k - 1 个元素,因为前 k - 1 大的元素都被弹出了,此时最大堆的堆顶元素就是数组中的第 `k` 个最大元素。
import java.util.PriorityQueue;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
// 使用一个含有 len 个元素的最大堆,lambda 表达式应写成:(a, b) -> b - a
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(len, (a, b) -> b - a);
for (int i = 0; i < len; i++) {
maxHeap.add(nums[i]);
}
for (int i = 0; i < k - 1; i++) {
maxHeap.poll();
}
return maxHeap.peek();
}
}
思路 3 参考代码
//思路 3 :只用 `k` 个容量的优先队列,而不用全部 `len` 个容量。
import java.util.PriorityQueue;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
// 使用一个含有 k 个元素的最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
for (int i = 0; i < k; i++) {
minHeap.add(nums[i]);
}
for (int i = k; i < len; i++) {
// 看一眼,不拿出,因为有可能没有必要替换
Integer topEle = minHeap.peek();
// 只要当前遍历的元素比堆顶元素大,堆顶弹出,遍历的元素进去
if (nums[i] > topEle) {
minHeap.poll();
minHeap.add(nums[i]);
}
}
return minHeap.peek();
}
}
思路 4 参考代码
//思路 4:用 `k + 1` 个容量的优先队列,使得上面的过程更“连贯”一些,到了 `k` 个以后的元素,就进来一个,出去一个,让优先队列自己去维护大小关系。
import java.util.PriorityQueue;
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
// 最小堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k + 1, (a, b) -> (a - b));
for (int i = 0; i < k; i++) {
priorityQueue.add(nums[i]);
}
for (int i = k; i < len; i++) {
priorityQueue.add(nums[i]);
priorityQueue.poll();
}
return priorityQueue.peek();
}
}
思路 5 参考代码
//思路 5:综合考虑以上两种情况,总之都是为了节约空间复杂度。即 `k` 较小的时候使用最小堆,`k` 较大的时候使用最大堆。
import java.util.PriorityQueue;
public class Solution {
// 根据 k 的不同,选最大堆和最小堆,目的是让堆中的元素更小
// 思路 1:k 要是更靠近 0 的话,此时 k 是一个较大的数,用最大堆
// 例如在一个有 6 个元素的数组里找第 5 大的元素
// 思路 2:k 要是更靠近 len 的话,用最小堆
// 所以分界点就是 k = len - k
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
if (k <= len - k) {
// System.out.println("使用最小堆");
// 特例:k = 1,用容量为 k 的最小堆
// 使用一个含有 k 个元素的最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
for (int i = 0; i < k; i++) {
minHeap.add(nums[i]);
}
for (int i = k; i < len; i++) {
// 看一眼,不拿出,因为有可能没有必要替换
Integer topEle = minHeap.peek();
// 只要当前遍历的元素比堆顶元素大,堆顶弹出,遍历的元素进去
if (nums[i] > topEle) {
minHeap.poll();
minHeap.add(nums[i]);
}
}
return minHeap.peek();
} else {
// System.out.println("使用最大堆");
assert k > len - k;
// 特例:k = 100,用容量为 len - k + 1 的最大堆
int capacity = len - k + 1;
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(capacity, (a, b) -> b - a);
for (int i = 0; i < capacity; i++) {
maxHeap.add(nums[i]);
}
for (int i = capacity; i < len; i++) {
// 看一眼,不拿出,因为有可能没有必要替换
Integer topEle = maxHeap.peek();
// 只要当前遍历的元素比堆顶元素大,堆顶弹出,遍历的元素进去
if (nums[i] < topEle) {
maxHeap.poll();
maxHeap.add(nums[i]);
}
}
return maxHeap.peek();
}
}
}