2020-03-02：在无序数组中，如何求第K小的数？
福哥答案2021-03-02：
1.堆排序。时间复杂度：O(N*lgK)。有代码。
2.单边快排。时间复杂度：O(N)。有代码。
3.bfprt算法。时间复杂度：O(N)。有代码。
代码用golang编写，代码如下：
package main
import (
"container/heap"
"fmt"
"math/rand"
"sort"
)
func main() {
//1 2 3 4 5 6 7
arr := []int{1, 2, 3, 4, 5, 10, 9, 8, 7, 6}
ret := minKth1(arr, 7)
fmt.Println("1.堆排序：", ret)
ret = minKth2(arr, 7)
fmt.Println("2.单边快排：", ret)
ret = minKth3(arr, 7)
fmt.Println("3.bfprt算法：", ret)
}
// 利用大根堆，时间复杂度O(N*logK)
func minKth1(arr []int, k int) int {
maxHeap := &IntHeap{}
heap.Init(maxHeap)
for i := 0; i < k; i++ {
heap.Push(maxHeap, arr[i])
}
for i := k; i < len(arr); i++ {
heap.Push(maxHeap, arr[i])
heap.Pop(maxHeap)
//heap.Push(maxHeap, arr[i])
}
return heap.Pop(maxHeap).(int)
}
type IntHeap sort.IntSlice
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return !(h[i] < h[j]) }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
//func (h IntHeap) Len() int { return sort.IntSlice(h).Len() }
//func (h IntHeap) Less(i, j int) bool { return !sort.IntSlice(h).Less(i, j) }
//func (h IntHeap) Swap(i, j int) { sort.IntSlice(h).Swap(i, j) }
func (h *IntHeap) Push(x interface{}) {
//fmt.Println("push----")
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
// 改写快排，时间复杂度O(N)
// k >= 1
func minKth2(arr []int, k int) int {
arrc := make([]int, len(arr))
copy(arrc, arr)
return process2(arrc, 0, len(arr)-1, k-1)
}
// arr 第k小的数
// process2(arr, 0, N-1, k-1)
// arr[L..R] 范围上，如果排序的话(不是真的去排序)，找位于index的数
// index [L..R]
func process2(arr []int, L int, R int, index int) int {
if L == R { // L = =R ==INDEX
return arr[L]
}
// 不止一个数 L + [0, R -L]
pivot := arr[L+rand.Intn(R-L)]
rang := partition(arr, L, R, pivot)
if index >= rang[0] && index <= rang[1] {
return arr[index]
} else if index < rang[0] {
return process2(arr, L, rang[0]-1, index)
} else {
return process2(arr, rang[1]+1, R, index)
}
}
func partition(arr []int, L int, R int, pivot int) []int {
less := L - 1
more := R + 1
cur := L
for cur < more {
if arr[cur] < pivot {
less++
arr[less], arr[cur] = arr[cur], arr[less]
cur++
} else if arr[cur] > pivot {
more--
arr[cur], arr[more] = arr[more], arr[cur]
} else {
cur++
}
}
return []int{less + 1, more - 1}
}
// 利用bfprt算法，时间复杂度O(N)
func minKth3(arr []int, k int) int {
arrc := make([]int, len(arr))
copy(arrc, arr)
return bfprt(arrc, 0, len(arr)-1, k-1)
}
// arr[L..R] 如果排序的话，位于index位置的数，是什么，返回
func bfprt(arr []int, L int, R int, index int) int {
if L == R {
return arr[L]
}
// L...R 每五个数一组
// 每一个小组内部排好序
// 小组的中位数组成新数组
// 这个新数组的中位数返回
pivot := medianOfMedians(arr, L, R)
rang := partition(arr, L, R, pivot)
if index >= rang[0] && index <= rang[1] {
return arr[index]
} else if index < rang[0] {
return bfprt(arr, L, rang[0]-1, index)
} else {
return bfprt(arr, rang[1]+1, R, index)
}
}
// arr[L...R] 五个数一组
// 每个小组内部排序
// 每个小组中位数领出来，组成marr
// marr中的中位数，返回
func medianOfMedians(arr []int, L int, R int) int {
size := R - L + 1
offset := 0
if size%5 != 0 {
offset = 1
}
mArr := make([]int, size/5+offset)
for team := 0; team < len(mArr); team++ {
teamFirst := L + team*5
// L ... L + 4
// L +5 ... L +9
// L +10....L+14
mArr[team] = getMedian(arr, teamFirst, getMin(R, teamFirst+4))
}
// marr中，找到中位数
// marr(0, marr.len - 1, mArr.length / 2 )
return bfprt(mArr, 0, len(mArr)-1, len(mArr)/2)
}
func getMedian(arr []int, L int, R int) int {
insertionSort(arr, L, R)
return arr[(L+R)/2]
}
func insertionSort(arr []int, L int, R int) {
for i := L + 1; i <= R; i++ {
for j := i - 1; j >= L && arr[j] > arr[j+1]; j-- {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}执行结果如下：
