题目描述

输入n个整数，找出其中最小的k个数。

注意：

数据保证k一定小于等于输入数组的长度;
输出数组内元素请按从小到大顺序排序;

样例

输入：[1,2,3,4,5,6,7,8] , k=4

输出：[1,2,3,4]

算法1

(基于快排/快选) $O(n + klogk)$

快排/快选每次会把区间分为两个部分，<=x 和 x<=。当调整到前面一部分的长度等于k的时候，就不在继续调整，返回。

时间复杂度

这里的快排/快选调整区间的时候只会递归调整两个子区间的一个，时间复杂度$O(n)$；
最后取出前k个元素，再做个排序，$O(klogk)$；
总的时间复杂度$O(n+klogk)$。

Python3 代码

class Solution(object):
    def getLeastNumbers_Solution(self, input, k):
        """
        :type input: list[int]
        :type k: int
        :rtype: list[int]
        """
        def quick_select(l, r, k):
            if l >= r:
                return
            mid = input[l + r >> 1]
            i, j = l - 1, r + 1
            while i < j:
                i += 1
                j -= 1
                while input[i] < mid: i += 1
                while input[j] > mid: j -= 1
                if i < j: input[i], input[j] = input[j], input[i]
            if k == j - l + 1: return
            if j - l + 1 > k: quick_select(l, j, k)
            elif j - l + 1 < k: quick_select(j + 1, r, k -j + l - 1)

        if not input:
            return []
        quick_select(0, len(input) -1 ,k)
        ans = input[: k]
        ans.sort()
        return ans