一、简介

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。

数据范围：0\le k,n \le 100000≤k,n≤10000，数组中每个数的大小0 \le val \le 10000≤val≤1000

要求：空间复杂度 O(n)O(n) ，时间复杂度 O(nlogn)O(nlogn)

示例1

输入：

[4,5,1,6,2,7,3,8],4

复制

返回值：

[1,2,3,4]

复制

说明：

返回最小的4个数即可，返回[1,3,2,4]也可以

题目来源：牛客

二、解法

知识点：堆、排序、分治

package main

type Heap struct {
	size  int  // 大小
	data []int // 数据
}


func GetLeastNumbers_Solution( input []int ,  k int ) []int {
	// write code here
	if k == 0 || len(input) == 0 {
		return nil
	}

	// 构建一个大小为 k的大堆
	minHeap := new(Heap)
	minHeap.size = k

	for _,v := range input {
		minHeap.Add(v)
	}

	return minHeap.data
}

func (h *Heap) Add(v int)  {
	if len(h.data) == 0 {
		h.data = []int{v}

		return
	}


	if len(h.data) < h.size {
		// 堆尚未满
		h.data = append(h.data, v)

		middleIndex := len(h.data) / 2 - 1
		for i := middleIndex; i>= 0; i -- {
			h.jumpData(i)
		}

		return
	}

	// 堆已满
	if h.data[0] <= v {// 若当前元素，大于堆顶元素，则丢失
		return
	}

	// 移除堆顶元素
	h.data[0] =v

	// 调整堆中元素
	h.jumpData(0)
}



func (h *Heap) jumpData(index int)  {
	leftIndex := 2*index +1
	rightIndex := 2 *index + 2

	if leftIndex >= len(h.data) {
		return
	}

	if rightIndex >= len(h.data) {
		// 仅仅有左边节点
		if h.data[leftIndex] < h.data[index] {
			return
		}

		// 交换左边节点和 当前节点
		h.data[leftIndex],  h.data[index] =  h.data[index], h.data[leftIndex]

		// 调整 leftIndex节点
		h.jumpData(leftIndex)
		return
	}

	// 根节点已是最大值
	if h.data[index] >= h.data[leftIndex] && h.data[index] >= h.data[rightIndex] {
		return
	}

	// left 节点是最大值
	if h.data[leftIndex] > h.data[index] && h.data[leftIndex] >= h.data[rightIndex] {
		// 交换左边节点和 当前节点
		h.data[leftIndex],  h.data[index] =  h.data[index], h.data[leftIndex]

		// 调整 leftIndex节点
		h.jumpData(leftIndex)

		return
	}

	// right 节点是最大值
	if h.data[rightIndex] > h.data[index] && h.data[rightIndex] >= h.data[leftIndex] {
		// 交换左边节点和 当前节点
		h.data[rightIndex],  h.data[index] =  h.data[index], h.data[rightIndex]

		// 调整 leftIndex节点
		h.jumpData(rightIndex)

		return
	}
}