2020-03-02：在无序数组中，如何求第K小的数？
福哥答案2021-03-02：
1.堆排序。工夫复杂度：O(N*lgK)。有代码。
2.单边快排。工夫复杂度：O(N)。有代码。
3.bfprt算法。工夫复杂度：O(N)。有代码。
代码用golang编写，代码如下：
package mainimport ( "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.IntSlicefunc (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 >= 1func 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代码
评论