3. Time: O(k) for popping top k elements to list, O(klogk) for build heap, O((n-k)logk) for updating heap, O(k) for reversing list and return result. So O(k+ nlogk)
4. Space: O(k) for heap
方法2：直接先通过min heap把整个list heapify，再pop到剩下k个element
Time: O(n +klogn) in total, O(n) for building heap, O(klogn) popping 最小的k个element
Space: O(n)
方法3： quickselect
3.Coding
import heapq
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
# base case: when k > tinput or k<1: return None
# method 2 : max-heap with k element
# pop the top k element to heap and then heapify max heap with K element
# iterate the n-k element
# if element > the top element in heap / max element in heap, skip
# else: pop the max element and append current element
# Finally we find the K smallest element in heap only
#
# Time O(klogk) for heapify + O((n-k)logk ) for popping and inserting element
# SO O(nlogk) in total
# #
# Space: O(k) for heap
#
#
#
if not tinput or (k > len(tinput) or k<1):
return []
#O(k)
heap = []
for i in range(k):
heap.append(-tinput.pop())
# O(klogk)
heapq.heapify(heap)
# O((n-k)logk)
for i in range(len(tinput)):
if -tinput[i] > heap[0]:
heapq.heappop(heap)
heapq.heappush(heap,-tinput[i])
#O(klogk)
res = []
while len(heap):
res.append(-heapq.heappop(heap))
# O(n)
res.reverse()
return res