2
go 快速排序TopK leetcode 251
source link: https://studygolang.com/articles/35279
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
求第K大数
已知一轮快排可以将一个数组分为两个部分，且两个部分有大小关系，利用这个关系来求解，每一轮快排都能缩小问题的范围，
func findKthLargest(nums []int, k int) int {
var l, r = 0, len(nums) - 1
return partition(nums, l, r, k)
}
func partition(arr []int,l int, r int, k int) int {
if l == r {
return arr[l]
}
var i, j int = l-1, r+1
var mid int = (l + r) / 2
var x int = arr[mid]
for i < j {
i++
for arr[i] > x {
i++
}
j--
for arr[j] < x {
j--
}
if i < j {
arr[i], arr[j] = arr[j], arr[i]
}
}
// l, j and j+1, r
var s1 int = j-l+1
if k <= s1 {
return partition(arr, l, j, k)
}
return partition(arr, j+1, r, k-s1)
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK