题解 | #最小的K个数#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param input int整型一维数组
 * @param k int整型
 * @return int整型一维数组
 */
//堆排序； -》k大的堆
// 实现一个int的heap
/*
type IntHeap []int

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] }

// Push 往堆中插入一个元素
func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

// Pop 从堆中弹出最大的元素
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	*h = old[0 : n-1]
	x := old[n-1]
	return x
}

func (h *IntHeap) ConvertToInt() []int {
	old := *h
	return old
}

func GetLeastNumbers_Solution(input []int, k int) []int {
	// write code here
	if k > len(input) {
		return input
	}
	if k == 0 {
		return []int{}
	}
	topK := &IntHeap{}
	heap.Init(topK)
	for i := 0; i < k; i++ {
		heap.Push(topK, input[i])
	}

	//后面的元素替换堆中存储的最大元素
	for i := k; i < len(input); i++ {
		tmp := heap.Pop(topK).(int)
		if tmp > input[i] {
			heap.Push(topK, input[i])
		} else {
			heap.Push(topK, tmp)
		}
	}
	return topK.ConvertToInt()
}
*/

//快速排序
/*
func partition(nums []int, l, r int) int {
	p := l
	i, j := l, r
	for i < j {
		//从左到右找到第一个比pivot大的值
		for i < j && nums[i] < nums[p] {
			i++
		}
		//从右到左找到第一个比pivot小的值
		for i<j && nums[j] >= nums[p] {
			j--
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	nums[p], nums[i] = nums[i], nums[p]
	return i
}

func findKthMinIndex(nums []int, l, r, k int) int {
	p := partition(nums, l, r)
	if p == k {
		return p
	}
	if p < k {
		return findKthMinIndex(nums, p+1, r, k)
	}
	return findKthMinIndex(nums, l, p-1, k)
}

func GetLeastNumbers_Solution(input []int, k int) []int {
	// write code here
	if k > len(input) {
		return input
	}
	if k == 0 {
		return []int{}
	}
	p := findKthMinIndex(input, 0, len(input)-1, k-1)
	return input[0 : p+1]
}
*/

//冒泡排序
func GetLeastNumbers_Solution(input []int, k int) []int {
	// write code here
	if k > len(input) {
		return input
	}
	if k == 0 {
		return []int{}
	}
	//从后往前冒泡k个数据
	for i := 0; i < k; i++ {
		for j := len(input) - 1; j > 0; j-- {
			if input[j] < input[j-1] {
				input[j], input[j-1] = input[j-1], input[j]
			}
		}
	}
	return input[:k]
}