LeetCode 215. 数组中的第K个最大元素
题目描述
思路分析
我们可以使用快速选择算法来解决这个问题。
- 选择一个基准元素。
- 将数组分为两部分：大于基准的元素和小于基准的元素。
- 根据
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
// 找到第 k 个最大的元素
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]
}
pivotIndex := partition(nums, left, right)
if k == pivotIndex {
return nums[k]
} else if k < pivotIndex {
return quickSelect(nums, left, pivotIndex-1, k)
} else {
return quickSelect(nums, pivotIndex+1, right, k)
}
}
// 分区函数
func partition(nums []int, left, right int) int {
pivotIndex := left + rand.Intn(right-left+1)
nums[pivotIndex], nums[right] = nums[right], nums[pivotIndex]
pivot := nums[right]
i := left
for j := left; j < right; j++ {
if nums[j] < pivot {
nums[i], nums[j] = nums[j], nums[i]
i++
}
}
nums[i], nums[right] = nums[right], nums[i]
return i
}
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
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！