题解 | #最小的K个数# go + 快排

快排

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param input int整型一维数组 
 * @param k int整型 
 * @return int整型一维数组
*/
func GetLeastNumbers_Solution(input []int ,  k int) []int {
    // write code here
    if len(input) == 0 {
        return input
    }
    if  k > len(input) || k == 0 {
        return nil
    }

//  找到前k个元素
    arr := findK(input, k)

//  对前k个元素排序
    fastSort(arr, 0, len(arr)-1)

    return arr
}

//  找到前k小元素
func findK(arr []int, k int) []int {
    res := make([]int, 0, k)

    var find func(arr []int, k int, l, r int) 
    find = func(arr []int, k int, l, r int) {
        left := l
        right:= r 
        target := arr[l]

        for l < r {
            for l < r && target <= arr[r] {
                r--
            }
            arr[l] = arr[r]

            for l<r && target >= arr[l] {
                l++
            }
            arr[r] = arr[l]
        }
        arr[l] = target

        if l > k {
            find(arr, k, left, l-1)
        }else if l < k {
            find(arr, k, l+1, right)
        } else if l == k {
//          找到了前k个元素（此时的k为数组下标k-1）
            for i := 0; i <= k; i++ {
                res = append(res, arr[i])
            }
        }
    }

    find(arr, k-1, 0, len(arr)-1)
    return res
}

// 快排， 对数组排序
func fastSort(arr []int, l, r int) {
    if l >= r {
        return
    }

    left := l
    right := r
    target := arr[l]

    for l < r {
        for l < r && target <= arr[r] {
            r--
        }
        arr[l] = arr[r]

        for l < r && target >= arr[l] {
            l++
        }
        arr[r] = arr[l]
    }

    arr[l] = target

    fastSort(arr, left, l-1)
    fastSort(arr, l+1, right)
}