class Solution:
def GetLeastNumbers_Solution(self, t, k):
# write code here
if len(t) == 0 or len(t) < k or k <=0:
#不设置k == 0 返回，k为0时会陷入无限循环
return []
s = 0
l = len(t) - 1
index = self.partition(t, s, l)
print('index1', index)
while index != (k - 1) :
if index > k - 1:
l = index - 1
#必须写为l = index - 1, s = index + 1
#否则s与partition返回的index相等时，会陷入无限循环
elif index < k - 1:
s = index + 1
index = self.partition(t, s, l)
print('index2',index)
return t[:k]
def partition(self, t, s, l):
p = t[s]
print('s,l',s,l)
print(t)
t[l], t[s] = t[s], t[l]
print(t)
small = s - 1
large = s
while large < l:
if t[large] < p:
small += 1
if large != small:
t[small], t[large] = t[large], t[small]
large += 1
# while t[large] >= p and large < l:
# large += 1
# if large != small:
# print(small, large)
# t[small], t[large] = t[large], t[small]
# small += 1
#
# print('hi:',t)
# large += 1
small += 1
t[small], t[l] = t[l], t[small]
#
print(t)
print(small)
return small
注意以上陷入无限循环的点。
求解最小的k个数，两种方法：1）先排序，在取前k个，快排最佳 ，以上便是 2）最小堆
