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`大的元素。 直接返回。
|
|||
|
|
|||
|
例如:
|
|||
|
![heap](../assets/problems/215.kth-largest-element-in-an-array-heap.jpg)
|
|||
|
|
|||
|
*时间复杂度*:`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
|
|||
|
|
|||
|
如下图:
|
|||
|
```
|
|||
|
![quick select](../assets/problems/215.kth-largest-element-in-an-array-quick-select.jpg)
|
|||
|
|
|||
|
*时间复杂度*:
|
|||
|
- 平均是:`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)
|