题解 | #最小K个值#
最小的K个数
http://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf
利用最小堆解决问题
def left(i): """ 求节点i的左子树 """ return 2 * i + 1 def right(i): """ 求节点i的右子树，在数组中，右子树比左子树大1 """ return left(i) + 1 def exchange(arr, i, j): """ 交换数组中两个位置的值 """ temp = arr[i] arr[i] = arr[j] arr[j] = temp def heapify(arr, i, size): """ 维护最小堆 """ l, r, small = left(i), right(i), 0 # small保存较小的那个值 if l < size and arr[l] < arr[i]: small = l else: small = i if r < size and arr[r] < arr[small]: small = r if small != i: # 当前节点与较小的值 exchange(arr, i, small) # 递归进行维护堆 heapify(arr, small, size) def make_heap(arr): """ 构建一个最小堆 """ alen = len(arr) for i in range(alen // 2, -1, -1): heapify(arr, i, alen) class Solution: def GetLeastNumbers_Solution(self, tinput: list, k): make_heap(tinput) alen = len(tinput) res = [] for i in range(k): # 从最小堆中取出第一个节点的值，这个值是最小值 res.append(tinput[0]) # 将当前节点废弃， exchange(tinput, 0, alen - 1) alen -= 1 # 重新维护堆 heapify(tinput, 0, alen) return res
