剑指offer：最小的k个数

题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

# -*- coding: utf-8 -*-# @Time         : 2019-07-08 21:09# @Author       : Jayce Wong# @ProjectName  : job# @FileName     : getLeastNumbers.py# @Blog         : https://blog.51cto.com/jayce1111# @Github       : https://github.com/SysuJayceclass Solution:    """    从数组中寻找最小的k个数字，一般来说最直接的做法就是先将这个数组排序，然后取最小的k个数字即可。    但是这样做的时间复杂度为O(nlogn)    解法1：    借鉴快排中partition()的做法，因为partition()每次可以确定一个下标的正确元素，并保证其左右与其    大小关系有序。所以只要我们通过partition()确定了下标为k-1的元素，那么其左边都是小于该元素的。    时间复杂度为O(n)    解法2：    可以维护一个容量为k的容器，然后遍历整个数组，如果遇到比容器中最大值要小的元素，那么就将这个元素    替换容器中的最大值。时间复杂度为O(nlogk)    """    def GetLeastNumbers_Solution1(self, tinput, k):        if k <= 0 or k > len(tinput):            return []        ans = tinput[:k]        for i in range(k, len(tinput)):            if tinput[i] < max(ans):                ans.remove(max(ans))                ans.append(tinput[i])        return sorted(ans)    def GetLeastNumbers_Solution2(self, tinput, k):        def partition(begin, end):            pos = begin            for i in range(begin, end):                if tinput[i] < tinput[end]:                    tinput[i], tinput[pos] = tinput[pos], tinput[i]                    pos += 1            tinput[end], tinput[pos] = tinput[pos], tinput[end]            return pos        if k <= 0 or k > len(tinput):            return []        start, stop = 0, len(tinput) - 1        idx = partition(start, stop)        while idx != k - 1:            if idx > k:                stop = idx - 1            else:                start = idx + 1            idx = partition(start, stop)        return sorted(tinput[: k])def main():    nums = [4, 5, 1, 6, 2, 7, 3, 8]    k = 4    solution = Solution()    print(solution.GetLeastNumbers_Solution2(nums, k))if __name__ == '__main__':    main()