牛客-剑指offer系列题解:最小的K个数

记录刷题的过程。牛客和力扣中都有相关题目，这里以牛客的题目描述为主。该系列默认采用python语言。
1、问题描述：
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

2、数据结构：
二叉树，堆

3、题解：
方法1：排序，取前k个数

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if len(tinput) < k or k<= 0:
            return []
        return sorted(tinput)[:k]

方法2：大根堆
查找最小的k个数，用大根堆；查找最大的K个数，用小根堆。
首先，由输入数组的前K个值，创建长度为K的大根堆，先把新值放到末尾，然后与父节点比较，大于父节点就交换；
然后比较与大根堆的根结点的关系，并调整大根堆，即遍历之后的数，判断每个数与大根堆的根节点的大小，小于根结点就把根节点替换掉，然后，循环判断与子节点的关系，小于子节点（与较大的子节点比较即可）则交换，知道叶子结点。

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        #大根堆
        #创建大根堆
        def createheap(arr):
            maxheap.append(arr)
            m = len(maxheap)
            currentindex = m - 1
            while currentindex != 0:
                parentindex = (m - 1 ) >> 1
                if maxheap[currentindex] > maxheap[parentindex]:
                    maxheap[currentindex],maxheap[parentindex] = maxheap[parentindex],maxheap[currentindex]
                else:
                    break
        #调整大根堆，头结点发生改变
        def adjustheap(arr):
            if arr < maxheap[0]:
                maxheap[0] = arr
            m = len(maxheap)
            index = 0
            while index < m:
                left = index * 2 + 1
                right = index * 2 + 2
                temp = 0
                if right < m:
                    if maxheap[left] < maxheap[right]:
                        temp = right
                    else:
                        temp = left
                elif left < m:
                    temp  = left
                else:
                    break

                if maxheap[index] < maxheap[temp]:
                    maxheap[index],maxheap[temp] = maxheap[temp],maxheap[index]
                index = temp

        n = len(tinput)
        if n < k or k <= 0:
            return []
        maxheap = []
        for i in range(n):
            if i < k:#创建大根堆
                createheap(tinput[i])
            else:#比较，调整大根堆
                adjustheap(tinput[i])
        return sorted(maxheap)

4、复杂度分析：
方法1：
时间复杂度：O(N*logN)
空间复杂度：O(logN)

方法2：
时间复杂度：O(N*logK)
空间复杂度：O(K)