主题思路
这里用快速选择比快排要更好
快速排序每次会选择两边来递归,时间复杂度是O(nlogn)
快速选择每次只会选择一边递归(一次分边L,R,当K小于等于L,说明第K小的数在本次分区的左边,下次只用递归左边;当K大于L,说明第K小的数在本次分区的右边,下次只用递归右边。而且当停止递归时,K会是这次分区的左边界),时间复杂度是O(n)
注意细节
一不小心就会拿快速排序来做此题
在用快速排序,注意第K个数 nums[K - 1]
带越位检测的快速选择
package main
import (
"errors"
"fmt"
"os"
"bufio"
)
const N int = 1e5 + 10
var (
out = bufio.NewWriter(os.Stdout)
in = bufio.NewReader(os.Stdin)
n, k int
nums [N]int
)
func quickPick(l, r, k int) (int, error) {
if k > n {
return -1, errors.New("越界")
}
if l >= r {
return nums[l], nil
}
i, j, x := l - 1, r + 1, nums[l + (r - l) >> 1]
for i < j {
for {
i++
if nums[i] >= x {break}
}
for {
j--
if nums[j] <= x {break}
}
if i < j {
nums[i], nums[j] = nums[j], nums[i]
}
}
if k <= j - l + 1 {
return quickPick(l, j, k)
} else {
return quickPick(j + 1, r, k - (j - l + 1))
}
}
func main() {
defer out.Flush()
fmt.Fscan(in, &n, &k)
for i := 0; i < n; i++ {
fmt.Fscan(in, &nums[i])
}
res, err := quickPick(0, n - 1, k)
if err == nil {
fmt.Fprintln(out, res)
}
}
标准写法 快速选择
最快写法
第二是快排, 第三是sort包
package main
import (
"fmt"
"bufio"
"os"
)
var (
N, K int
nums []int
in = bufio.NewReader(os.Stdin)
out = bufio.NewWriter(os.Stdout)
)
func quickSort(l, r, K int) int { // 核心:快速选择
if l >= r { return nums[l] } // 当停止递归时,K就是左边界
x := nums[l + (r - l) >> 1]
i, j := l - 1, r + 1
for i < j {
for { i++; if nums[i] >= x { break } }
for { j--; if nums[j] <= x { break } }
if i < j { nums[i], nums[j] = nums[j], nums[i] }
}
if j - l + 1 >= K {
return quickSort(l, j, K) // 第K小的数在左边,下次递归左边
} else {
return quickSort(j + 1, r, K - (j - l + 1)) // 第K小的数在右边,下次递归右边
}
}
func main() {
fmt.Fscan(in, &N, &K)
nums = make([]int, N)
for i := 0; i < N; i++ { fmt.Fscan(in, &nums[i]) }
fmt.Fprintf(out, "%d", quickSort(0, N - 1, K))
out.Flush()
}
标准写法(全排序)
package main
import (
"fmt"
"bufio"
"os"
)
var (
N, K int
nums []int
in = bufio.NewReader(os.Stdin)
out = bufio.NewWriter(os.Stdout)
)
func quickSort(l, r int) {
if l >= r { return }
x := nums[l + (r - l) >> 1]
i, j := l - 1, r + 1
for i < j {
for { i++; if nums[i] >= x { break } }
for { j--; if nums[j] <= x { break } }
if i < j { nums[i], nums[j] = nums[j], nums[i] }
}
quickSort(l, j)
quickSort(j + 1, r)
}
func main() {
fmt.Fscan(in, &N, &K)
nums = make([]int, N)
for i := 0; i < N; i++ { fmt.Fscan(in, &nums[i]) }
quickSort(0, N - 1)
fmt.Fprintf(out, "%d", nums[K - 1])
out.Flush()
}
“邪道”写法(全排序)
package main
import (
"fmt"
"bufio"
"os"
"sort"
)
var (
N, K int
nums []int
in = bufio.NewReader(os.Stdin)
out = bufio.NewWriter(os.Stdout)
)
func main() {
fmt.Fscan(in, &N, &K)
nums = make([]int, N)
for i := 0; i < N; i++ { fmt.Fscan(in, &nums[i]) }
sort.Ints(nums)
fmt.Fprintf(out, "%d", nums[K - 1])
out.Flush()
}