LeetCode 215. 数组中的第 K 个最大元素
题目描述
思路分析
小顶堆
快速选择算法
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func findKthLargest(nums []int, k int) int {
return quickSelect(nums, 0, len(nums)-1, len(nums)-k)
}
func quickSelect(nums []int, left, right, k int) int {
if left >= right {
return nums[left]
}
pointIndex := partition(nums, left, right)
if k == pointIndex {
return nums[k]
} else if k < pointIndex {
return quickSelect(nums, left, pointIndex-1, k)
} else {
return quickSelect(nums, pointIndex+1, right, k)
}
}
func partition(nums []int, left, right int) int {
pointIndex := rand.Intn(right-left+1) + left
nums[left], nums[pointIndex] = nums[pointIndex], nums[left]
point := nums[left]
i, j := left, right
for i < j {
for i < j && nums[j] >= point {
j--
}
if i < j {
nums[i] = nums[j]
i++
}
for i < j && nums[i] <= point {
i++
}
if i < j {
nums[j] = nums[i]
j--
}
}
nums[i] = point
return i
}
1
write your code here
相似题目
| 题目 | 难度 | 题解 |
|---|---|---|
| 摆动排序 II | Medium | |
| 前 K 个高频元素 | Medium | |
| 第三大的数 | Easy | |
| 数据流中的第 K 大元素 | Easy | |
| 最接近原点的 K 个点 | Medium |
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！