xiedaxia1hao
commented
3 years ago 模版题：215. Kth Largest Element in an Array
Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
学会如何从O(nlgn) -> O(nlgk) -> O(n)!!
这道题让我们求一个数组里面第k大的数字。
比如 [1, 3, 5, 2, 6, 4] 这个数组中，让我们求k=2大的数的话，最容易想到的方法是把整个数组先sort一下，然后 return nums[arr.length-k+1] 即可。
这种做法的复杂度是O(nlgn)，可以优化一下吗？
我们可以尝试一下使用minHeap：
- 我们可以维护一个size=k的最小堆，不断把数组里的数字加进去，直到size=k
- 之后，每当我们加一个元素进去的时候，因为现在的size=k+1，我们需要把heap里多余的数字给poll出来。根据heap的原理，这个时候poll出来的就是当前k+1个数字中最小的数字。
- 当我们把所有数字都加进去之后，这个时候heap的peek就是当前数组最大的k个数字中，最小的一个，即kth largest element。
我们用数组 [1, 3, 5, 2, 6, 4]，k=4 来举个例子：
- 首先我们将前4个元素直接放到heap中，当前我们heap就是：
[1, 3, 5, 2] - 然后我们尝试把6加入到heap中，此时我们的heap就是:
[1, 3, 5, 2, 6]。但是因为我们当前heap的size是5，我们需要除掉一个多余的数字。因为是最小堆，我们要除掉的是1。此时我们的heap就是：[3, 5, 2, 6] - 同理，我们把4加入到heap中，得到
[3, 5, 2, 6, 4]，除掉当前heap中最小的元素，得到:[3, 5, 6, 4] - 此时heap里保存的
[3, 5, 6, 4]就是原数组[1, 3, 5, 2, 6, 4]里最大的4个数字，这个时候，heap的顶端元素3就是最大的4哥数字中，最小的一个，即第4大的元素。
这样做的话，时间复杂度是多少呢？
- 我们把前面k个元素放进heap中，复杂度是O(klgk)
- 之后(n-k)的元素在入堆时，最差的情况就是所有元素都要导致heap重新排列，那这一部分的复杂度就是O((n-k)lgk)
- 所以总的时间复杂度就是 O(klgk + (n-k)lgk) -> O(nlgk)，比暴力的O(nlgn)好了不少。
当然了，这题用maxHeap也可以，我们把所有的元素放到heap里，我们需要poll出去k-1个元素，然后此时heap的root就是我们的kth largest element了。 但是这样的话，空间复杂度就大了，因为我们最大要保存n个元素，而minHeap可以保证我们的size是 <= k的。
代码如下：
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(int num : nums) {
minHeap.offer(num);
if(minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
}这里介绍一个quick select的方法，可以把复杂度优化到O(n)，虽然和这个专题里的pattern没什么关系，但是因为这题实在是经典，quick select的方法也是需要掌握的。
class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
int left = 0, right = n-1;
Random rand = new Random(0);
while(left <= right) {
int chosenPivotIndex = rand.nextInt(right-left+1) + left;
int finalPivotIndedx = partition(nums, left, right, chosenPivotIndex);
if(finalPivotIndedx == n-k) {
return nums[finalPivotIndedx];
} else if(finalPivotIndedx < n-k) {
left = finalPivotIndedx+1;
} else {
right = finalPivotIndedx-1;
}
}
return -1;
}
public int partition(int[] nums, int left, int right, int pivotIndex) {
int pivotValue = nums[pivotIndex];
swap(nums, right, pivotIndex);
int i = left;
for(int j = left; j < right; j++) {
if(nums[j] < pivotValue) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, right);
return i;
}
public void swap(int[] nums, int first, int second) {
int temp = nums[first];
nums[first] = nums[second];
nums[second] = temp;
}
}Quick select的时间复杂度怎么算呢？
我们可以用递推式来想：
每一轮我们都会把我们的数组变成其中的一半，然后对于每一步来说，如果当前的数组长度为n，我们要做n-1次comparison来得到最终的答案，那我们最后的递推式就是：
T(n) = T(n/2) + (n-1)
具体的解法就是：
经常会有问题让我们求某个list里面的top/smallest/frequent K elements。比如经典的 215. Kth Largest Element in an Array 就是一道常见的面试题。
这一类问题，因为要维护一个size为k的set，通常情况下我们可以用heap来帮助我们解题。
在针对一些特定的题目，比如求top k appeared frequency的题目，我们可以用bucket sort来进一步优化。
这样说有一些抽象，下面就直接看例题吧。