题解 | #最小的K个数#

package main



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

	return r[:k]

}

func MergeSort1(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	mid := len(arr) / 2
	left := MergeSort1(arr[:mid])
	right := MergeSort1(arr[mid:])

	return merge1(left, right)
}

func merge1(left, right []int) []int {
	res := make([]int, 0, len(right)+len(left))
	i, j := 0, 0

	for i < len(left) && j < len(right) {
		if left[i] < right[j] {
			res = append(res, left[i])
			i++
		} else {
			res = append(res, right[j])
			j++
		}
	}
	res = append(res, left[i:]...)
	res = append(res, right[j:]...)

	return res
}