题目:输入M个数,从中找到K个最小的数
比如输入10,-9,0,100,90,1,4,-9;找到最小的3个数为:-9,-9,0
1这道题最坏的办法是对M个数进行排序,排序算法最好的时间复杂度是o(mlogm)
2 第二种办法,是对其中的K个数进行排序,时间复杂度是o(m*k*logk),这要对比m和k*logk的大小,看哪个办法更优
3 对于第二种方法的一个优化是,不需要对K个数进行排序,只需要要到这K个数中最大的数A,然后下一个数跟A对比,比A大则不要,比A小则入选,如此循环;时间复杂度是o(m*k)
4 最后一种是对方法3的一个优化,在找数组K个数中最大数时,最好的时间复杂度是用大根堆的方式,时间复杂度是logk,整体的时间复杂度是o(m*logk)。
代码思路:
对前k个数,进行建立大根堆;建立大根堆时,从(k-1)/2的位置开始向上进行调整;
然后对后面m-k个数据,一个数据一个数据的与堆的根节点进行大小对比,比根节点小的,用这个值替换根节点,然后在从根节点对堆进行调整。
这样最后堆里的内容就是要输出的内容
下面是第四种方式的代码:
'''
查找最小的k个元素
题目:输入n个整数,输出其中最小的k个。
例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4
'''
def adjustHeap(heap, page):
'''
堆的调整
param:heap是堆的数组,page是需要调整的节点
'''
temp = page
#找page和page左节点和右节点三个点中,最大的一个点
if 2*temp+1 < len(heap):
if heap[2*temp+1] > heap[temp]:
temp = 2*temp+1
if 2*temp+2 < len(heap):
if heap[2*temp+2] > heap[temp]:
temp = 2*temp+2
#调整用最大的节点作为根节点,然后在对调整后的节点继续做调整
if temp != page:
temp_data = heap[page]
heap[page] = heap[temp]
heap[temp] = temp_data
adjustHeap(heap, temp)
if __name__ == "__main__":
m = [10,-9,0,100,90,1,4,-9]
k = 7
heap = []
len_m = len(m)
#对异常输入做返回
if k <=0 or len_m<=0 or k > len_m:
print None
#如果长度相当直接返回
else:
if k==len_m:
print m
else:
#否则先对前k个节点,从后向前调整
heap = m[:k]
index = (k-1)/2
while index >= 0:
adjustHeap(heap, index)
index = index - 1
tail = k-len_m
m = m[tail:]
#然后在用后面的数据跟根节点进行大小比较,如果比根节点小,则替换根节点,在从上向下做调整
for i in m:
if i < heap[0]:
heap[0] = i
adjustHeap(heap, 0)
print heap
输出:[90, 10, 1, -9, -9, 0, 4]