AcWing 53. 最小的k个数
原题链接
简单
作者:
buchiyu
,
2021-05-21 10:32:30
,
所有人可见
,
阅读 320
糟糕的算法
class Solution(object):
def getMinK(self, q, l, r, k):
# if l == r: return
i = l - 1
j = r + 1
x = q[l + r >> 1]
while i < j:
i += 1
while q[i] < x:
i += 1
j -= 1
while q[j] > x:
j -= 1
if i < j:
q[i], q[j] = q[j], q[i]
length = j - l + 1
if k < length:
return self.getMinK(q, l, j, k)
elif k > length:
res = q[l : j + 1] + self.getMinK(q, j + 1, r, k - length)
res.sort()
return res
else:
res = q[l : j + 1]
res.sort()
return res
def getLeastNumbers_Solution(self, input, k):
"""
:type input: list[int]
:type k: int
:rtype: list[int]
"""
length = len(input)
if length == 0: return []
return self.getMinK(input, 0, length - 1, k)