40.md

最小的K个数

题目

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

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

示例

输入：[4,5,1,6,2,7,3,8],4

返回值：[1,2,3,4]

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

思路

• 根据题意，那么排序，截取一段即可
• 关键是要求时间复杂度 O(nlogn)
• 那么就需要使用快排或者堆排序

堆排序

堆

• 堆是一种特殊的完全二叉树
• 其特点是父节点的值大于等于或小于等于子节点的值
• 父节点的值[大于等于]子节点的值的为大顶堆
• 父节点的值[小于等于]子节点的值的为小顶堆
• 把一个完全二叉树[逐层遍历]后得到一个序列，放在数组里
• 数组中第 i 个元素的子节点位于 2i+1 和 2i+2

构建一个堆

• 一个数组可以在 O(n) 时间内转换成一个最大堆
• 将输入数组看作一个堆，它尚未满足堆特性
• 从倒数第二层开始对堆上的节点进行遍历[即叶节点上面的一层[]直到[根节点]
• 对每个节点，将它向下传送，直到它已经比它的两个子节点都大。向下传送时，总是与较大的子节点进行交换

堆排序

• 从输入数组构建一个最大堆，这需要 O(n) 的时间
• 从堆中弹出元素放到输出数组中，从后往前填充，每次从堆中弹出元素需要 O(log n) 时间
• 整个容器加起来为 O(n * log n)
• 大顶堆排序后是升序，小顶堆排序后是降序

实现

func GetLeastNumbers_Solution(input []int, k int) []int {
	// 参数检查
	if len(input) == 0 || k <= 0 {
		return []int{}
	}
	if k >= len(input) {
		return input
	}
	var max func(int, int)
	max = func(i int, length int) {
		left := 2*i + 1
		right := 2*i + 2
		largest := 0
		if left < length && input[left] > input[i] {
			largest = left
		} else {
			largest = i
		}
		if right < length && input[right] > input[largest] {
			largest = right
		}
		if largest != i {
			input[i], input[largest] = input[largest], input[i]
			// 比较其父节点
			max(largest, length)
		}
	}
	// 建堆
	length := len(input)
	for i := length/2 - 1; i >= 0; i-- {
		max(i, length)
	}
	// 排序
	for i := length - 1; i > 0; i-- {
		// 将当前最大 { input[0] } 的放在队尾 { input[i] }
		input[i], input[0] = input[0], input[i]
		// 堆的大小减 1
		length--
		// 在小堆上重建堆
		max(0, length)
	}
	return input[:k]
}

一个大顶堆排序的过程

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

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