第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0215. 数组中的第 K 个最大元素

题目地址(215. 数组中的第K个最大元素)

题目描述

1
在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
2
3
示例 1:
4
5
输入: [3,2,1,5,6,4] 和 k = 2
6
输出: 5
7
示例 2:
8
9
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
10
输出: 4
11
说明:
12
13
你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。
Copied!

前置知识

  • Quick Select

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这道题要求在一个无序的数组中,返回第K大的数。根据时间复杂度不同,这题有3种不同的解法。

解法一 (排序)

很直观的解法就是给数组排序,这样求解第K大的数,就等于是从小到大排好序的数组的第(n-K)小的数 (n 是数组的长度)。
例如:
1
[3,2,1,5,6,4], k = 2
2
1. 数组排序:
3
[1,2,3,4,5,6],
4
2. 找第(n-k)小的数
5
n-k=4, nums[4]=5 (第2大的数)
Copied!
时间复杂度: O(nlogn) - n 是数组长度。

解法二 - 小顶堆(Heap)

可以维护一个大小为K的小顶堆,堆顶是最小元素,当堆的size > K 的时候,删除堆顶元素. 扫描一遍数组,最后堆顶就是第K大的元素。 直接返回。
例如:
时间复杂度O(n * logk) , n is array length 空间复杂度O(k)
跟排序相比,以空间换时间。

解法三 - Quick Select

Quick Select 类似快排,选取pivot,把小于pivot的元素都移到pivot之前,这样pivot所在位置就是第pivot index 小的元素。 但是不需要完全给数组排序,只要找到当前pivot的位置是否是在第(n-k)小的位置,如果是,找到第k大的数直接返回。
具体步骤:
1
1. 在数组区间随机取`pivot index = left + random[right-left]`.
2
2. 根据pivot 做 partition,在数组区间,把小于pivot的数都移到pivot左边。
3
3. 得到pivot的位置 index,`compare(index, (n-k))`.
4
a. index == n-k -> 找到第`k`大元素,直接返回结果。
5
b. index < n-k -> 说明在`index`右边,继续找数组区间`[index+1, right]`
6
c. index > n-k -> 那么第`k`大数在`index`左边,继续查找数组区间`[left, index-1]`.
7
8
例子,【3,2,3,1,2,4,5,5,6], k = 4
9
10
如下图:
Copied!
quick select
时间复杂度
  • 平均是:O(n)
  • 最坏的情况是:O(n * n)

关键点分析

  1. 1.
    直接排序很简单
  2. 2.
    堆(Heap)主要是要维护一个K大小的小顶堆,扫描一遍数组,最后堆顶元素即是所求。
  3. 3.
    Quick Select, 关键是是取pivot,对数组区间做partition,比较pivot的位置,类似二分,取pivot左边或右边继续递归查找。

代码(Java code)

解法一 - 排序
1
class KthLargestElementSort {
2
public int findKthlargest2(int[] nums, int k) {
3
Arrays.sort(nums);
4
return nums[nums.length - k];
5
}
6
}
Copied!
解法二 - Heap (PriorityQueue)
1
class KthLargestElementHeap {
2
public int findKthLargest(int[] nums, int k) {
3
PriorityQueue<Integer> pq = new PriorityQueue<>();
4
for (int num : nums) {
5
pq.offer(num);
6
if (pq.size() > k) {
7
pq.poll();
8
}
9
}
10
return pq.poll();
11
}
12
}
Copied!
解法三 - Quick Select
1
class KthLargestElementQuickSelect {
2
static Random random = new Random();
3
public int findKthLargest3(int[] nums, int k) {
4
int len = nums.length;
5
return select(nums, 0, len - 1, len - k);
6
}
7
8
private int select(int[] nums, int left, int right, int k) {
9
if (left == right) return nums[left];
10
// random select pivotIndex between left and right
11
int pivotIndex = left + random.nextInt(right - left);
12
// do partition, move smaller than pivot number into pivot left
13
int pos = partition(nums, left, right, pivotIndex);
14
if (pos == k) {
15
return nums[pos];
16
} else if (pos > k) {
17
return select(nums, left, pos - 1, k);
18
} else {
19
return select(nums, pos + 1, right, k);
20
}
21
}
22
23
private int partition(int[] nums, int left, int right, int pivotIndex) {
24
int pivot = nums[pivotIndex];
25
// move pivot to end
26
swap(nums, right, pivotIndex);
27
int pos = left;
28
// move smaller num to pivot left
29
for (int i = left; i <= right; i++) {
30
if (nums[i] < pivot) {
31
swap(nums, pos++, i);
32
}
33
}
34
// move pivot to original place
35
swap(nums, right, pos);
36
return pos;
37
}
38
39
private void swap(int[] nums, int i, int j) {
40
int tmp = nums[i];
41
nums[i] = nums[j];
42
nums[j] = tmp;
43
}
44
}
Copied!

参考(References)