AcWing 53. 最小的k个数
原题链接
简单
作者:
Sei
,
2019-08-31 21:09:36
,
所有人可见
,
阅读 694
python 代码,可以直接维护堆,不过没必要,正好直接练练堆排序,反正时间复杂度差不多
class Solution(object):
def getLeastNumbers_Solution(self, num, k):
"""
:type input: list[int]
:type k: int
:rtype: list[int]
"""
def heapify(num, i, n):
if i<n:
l, r, m = 2*i+1, 2*i+2, i
if l<n and num[l]>num[m]:
m = l
if r<n and num[r]>num[m]:
m = r
if i!=m:
num[m], num[i] = num[i], num[m]
heapify(num, m, n)
size = len(num)
parent = (size-2)/2
for i in range(parent, -1, -1):
heapify(num, i, size)
for i in range(size-1, -1, -1):
num[0], num[i] = num[i], num[0]
heapify(num, 0, i)
return num[:k]