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}
}执行后果如下：
左神 java 代码
评论