155 lines
4.7 KiB
Markdown
155 lines
4.7 KiB
Markdown
## 题目地址
|
||
https://leetcode.com/problems/kth-largest-element-in-an-array/
|
||
|
||
## 题目描述
|
||
|
||
```
|
||
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
|
||
|
||
Example 1:
|
||
|
||
Input: [3,2,1,5,6,4] and k = 2
|
||
Output: 5
|
||
Example 2:
|
||
|
||
Input: [3,2,3,1,2,4,5,5,6] and k = 4
|
||
Output: 4
|
||
Note:
|
||
You may assume k is always valid, 1 ≤ k ≤ array's length.
|
||
```
|
||
|
||
## 思路
|
||
|
||
这道题要求在一个无序的数组中，返回第K大的数。根据时间复杂度不同，这题有3种不同的解法。
|
||
|
||
#### 解法一 （排序）
|
||
很直观的解法就是给数组排序，这样求解第`K`大的数，就等于是从小到大排好序的数组的第`(n-K)`小的数 (n 是数组的长度）。
|
||
|
||
例如：
|
||
```
|
||
[3,2,1,5,6,4], k = 2
|
||
1. 数组排序：
|
||
[1,2,3,4,5,6]，
|
||
2. 找第（n-k）小的数
|
||
n-k=4, nums[4]=5 (第2大的数）
|
||
```
|
||
*时间复杂度:* `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. 在数组区间随机取`pivot index = left + random[right-left]`.
|
||
2. 根据pivot 做 partition，在数组区间，把小于pivot的数都移到pivot左边。
|
||
3. 得到pivot的位置 index，`compare(index, (n-k))`.
|
||
a. index == n-k -> 找到第`k`大元素，直接返回结果。
|
||
b. index < n-k -> 说明在`index`右边，继续找数组区间`[index+1, right]`
|
||
c. index > n-k -> 那么第`k`大数在`index`左边，继续查找数组区间`[left, index-1]`.
|
||
|
||
例子，【3,2,3,1,2,4,5,5,6]， k = 4
|
||
|
||
如下图：
|
||
```
|
||
|
||
|
||
*时间复杂度*：
|
||
- 平均是：`O(n)`
|
||
- 最坏的情况是：`O(n * n)`
|
||
|
||
## 关键点分析
|
||
1. 直接排序很简单
|
||
2. 堆（Heap）主要是要维护一个K大小的小顶堆，扫描一遍数组，最后堆顶元素即是所求。
|
||
3. Quick Select, 关键是是取pivot，对数组区间做partition，比较pivot的位置，类似二分，取pivot左边或右边继续递归查找。
|
||
|
||
## 代码（Java code）
|
||
*解法一 - 排序*
|
||
```java
|
||
class KthLargestElementSort {
|
||
public int findKthlargest2(int[] nums, int k) {
|
||
Arrays.sort(nums);
|
||
return nums[nums.length - k];
|
||
}
|
||
}
|
||
```
|
||
|
||
*解法二 - Heap （PriorityQueue）*
|
||
```java
|
||
class KthLargestElementHeap {
|
||
public int findKthLargest(int[] nums, int k) {
|
||
PriorityQueue<Integer> pq = new PriorityQueue<>();
|
||
for (int num : nums) {
|
||
pq.offer(num);
|
||
if (pq.size() > k) {
|
||
pq.poll();
|
||
}
|
||
}
|
||
return pq.poll();
|
||
}
|
||
}
|
||
```
|
||
|
||
*解法三 - Quick Select*
|
||
```java
|
||
class KthLargestElementQuickSelect {
|
||
static Random random = new Random();
|
||
public int findKthLargest3(int[] nums, int k) {
|
||
int len = nums.length;
|
||
return select(nums, 0, len - 1, len - k);
|
||
}
|
||
|
||
private int select(int[] nums, int left, int right, int k) {
|
||
if (left == right) return nums[left];
|
||
// random select pivotIndex between left and right
|
||
int pivotIndex = left + random.nextInt(right - left);
|
||
// do partition, move smaller than pivot number into pivot left
|
||
int pos = partition(nums, left, right, pivotIndex);
|
||
if (pos == k) {
|
||
return nums[pos];
|
||
} else if (pos > k) {
|
||
return select(nums, left, pos - 1, k);
|
||
} else {
|
||
return select(nums, pos + 1, right, k);
|
||
}
|
||
}
|
||
|
||
private int partition(int[] nums, int left, int right, int pivotIndex) {
|
||
int pivot = nums[pivotIndex];
|
||
// move pivot to end
|
||
swap(nums, right, pivotIndex);
|
||
int pos = left;
|
||
// move smaller num to pivot left
|
||
for (int i = left; i <= right; i++) {
|
||
if (nums[i] < pivot) {
|
||
swap(nums, pos++, i);
|
||
}
|
||
}
|
||
// move pivot to original place
|
||
swap(nums, right, pos);
|
||
return pos;
|
||
}
|
||
|
||
private void swap(int[] nums, int i, int j) {
|
||
int tmp = nums[i];
|
||
nums[i] = nums[j];
|
||
nums[j] = tmp;
|
||
}
|
||
}
|
||
```
|
||
|
||
## 参考（References）
|
||
1. [Quick Select Wiki](https://en.wikipedia.org/wiki/Quickselect) |