func QuickSelect(nums []int, start, end, k int) int {
if start == end {
return nums[start]
}
pivot := Partition(nums, start, end)
if k == pivot {
return nums[k]
} else if k < pivot {
return QuickSelect(nums, start, pivot-1, k)
} else {
return QuickSelect(nums, pivot+1, end, k)
}
}
func Partition(nums []int, start, end int) int {
rand.Seed(time.Now().UnixNano())
pivotIndex := rand.Intn(end - start + 1) + start
nums[pivotIndex], nums[end] = nums[end], nums[pivotIndex]
pivot := nums[end]
i := start - 1
for j := start; j < end; j++ {
if nums[j] <= pivot {
i++
nums[i], nums[j] = nums[j], nums[i]
}
}
nums[i+1], nums[end] = nums[end], nums[i+1]
return i + 1
}
Notion 写文章还是挺爽的，不知道收不收录