讨论/《排序算法全解析》 - 剑指 Offer 40. 最小的 k 个数/
《排序算法全解析》 - 剑指 Offer 40. 最小的 k 个数
class Solution(object):
    def getLeastNumbers(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: List[int]
        """
        n = len(arr)
        for i in range(n // 2 - 1, -1, -1):
            self.build_heap(arr, i, n-1)
        for j in range(k):
            arr[0], arr[n-j-1] = arr[n-j-1], arr[0]
            self.build_heap(arr, 0, n-j-2)
        return arr[n-k:]

    def build_heap(self, nums, i, l):
        left, right = 2*i+1, 2*i+2
        min_index = i
        if left <= l and nums[min_index] > nums[left]:
            min_index = left
        if right <= l and nums[min_index] > nums[right]:
            min_index = right
        if min_index != i:
            nums[i], nums[min_index] = nums[min_index], nums[i]
            self.build_heap(nums, min_index, l)
    
展开全部 3 讨论