题解 | #最小的K个数#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param input int整型一维数组 
 * @param k int整型 
 * @return int整型一维数组
*/
func GetLeastNumbers_Solution( input []int ,  k int ) []int {
    arr := input
	if k == 0 || len(arr) == 0 {
		return []int{}
	}
	quickSort(arr, 0, len(arr)-1)
	res := make([]int, 0)
	for i := 0; i < k; i++ {
		res = append(res, arr[i])
	}
	return res
}

// 从小到大
func quickSort(arr []int, left, right int) {
	if left >= right {
		return
	}
	pivot := getPivot(arr, left, right)
	quickSort(arr, left, pivot-1)
	quickSort(arr, pivot+1, right)
}

func getPivot(arr []int, left, right int) int {
	base := left
	for left < right {
		//从右边开始遍历
		for left < right && arr[right] >= arr[base] {
			right--
		}
		//从左边遍历
		for left < right && arr[left] <= arr[base] {
			left++
		}
		//交换
		arr[left], arr[right] = arr[right], arr[left]
	}
	//交换base、left
	arr[base], arr[left] = arr[left], arr[base]
	return left
}