剑指offer刷题日记29（python）

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

思路

第一个想法是对数组进行排序，然后返回排序之后的数组前k个数。但是这种方法需要一个长度为数组长度的空间，当数组很大时，效率不高。

因此，我们可以构建一个堆，

利用堆排序，适合处理海量数据

(1)遍历输入数组，将前k个数插入到推中；（利用heapq模块来做为堆的实现）

(2)继续从输入数组中读入元素做为待插入整数，并将它与堆中最大值比较：

如果待插入的值比当前已有的最大值小，则用这个数替换当前已有的最大值；

如果待插入的值比当前已有的最大值还大，则抛弃这个数，继续读下一个数。

这样动态维护堆中这k个数，以保证它只储存输入数组中的前k个最小的数，最后输出堆即可。这种方法只需要开辟一个长度为k的空间，大大节省了空间的消耗

代码

# -*- coding:utf-8 -*-import heapq # 利用python的heapq模块，来实现堆的操作class Solution: def GetLeastNumbers_Solution(self, tinput, k):# write code heremaxheap = []if k <= 0 or tinput == None or len(tinput)<k:return []for i in range(k):heapq.heappush(maxheap,-tinput[i])for i in range(k,len(tinput)):if maxheap[0]> -tinput[i]:continueelse:heapq.heappushpop(maxheap,-tinput[i])result = []for i in range(k):result.insert(0,-heapq.heappop(maxheap))return result

ps：heapq构造的是小顶堆，即堆顶元素最小，因此为了构造大顶堆，需要将元素都加负号，来颠倒他们的大小关系，相反数的小顶堆，就相当于原来数的大顶堆。求前K个最大的数，用小顶堆，K个小的数，用大顶堆。