关于福大大架构师每日一题:20200302在无序数组中如何求第K小的数

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 代码
评论