题目分析

这个题目太经典了，面试时遇到了两次，刷题时遇到了两次，虽然题目很简单，但是却暗藏杀机。

排序

当然了这个方法是最简单的，也是最没用的。因为面试官一定不想听到这样的解法，你他喵的在逗我？这种侮辱智商的解法，怎么会出现在这里？不过我在这里还是写一下代码的实现，虽然这种方法时间复杂度最高为$O(nlog(n))$，空间复杂度为$O(1)$，但是速度却很快，因为sorted函数太强大了。

1
2
3

class Solution:
    def getLeastNumbers(self, arr, k):
        return sorted(arr)[:k]

最大堆

k个最小值则需要维护一个大小为k的最大堆，因为堆顶元素为堆中的最大值。当新来的元素小于堆中的最大值时，则将堆顶元素弹出，插入该元素，否则新来的元素一定大于堆中的所有元素，不用操作即可。这种方法的时间复杂度为$O(nlog(k))$，空间复杂度为$O(k)$。当内存较小，数据量较大的时候常常使用，因为无法获取所有数据进行排序。

在Python中heapq库中的堆默认为最小堆，因此可以将数据加负号放入堆中，实现最大堆。

import heapq


class Solution:
    def getLeastNumbers(self, arr, k):
        if k == 0:
            return []
        hp = [-x for x in arr[:k]]
        heapq.heapify(hp)
        for i in range(k, len(arr)):
            if -hp[0] > arr[i]:
                heapq.heappushpop(hp, -arr[i])
        ans = [-x for x in hp]
        return ans

快速排序思想

在快速排序中，我们选择一个基准值，将小于等于基准值的元素放在基准值的左边，大于基准值的元素放在基准值的右边，因此会出现三种情况。
当基准值左边的元素个数等k时，则已经找到k个，不需要进行后面的排序。
当基准值左边的元素个数大于k时，右边的元素一定不在top k中，因此右边部分不需要处理，所以只需要递归左边部分即可。
当基准值左边的元素个数小于k时，左边的元素一定在top k中，因此左边部分不需要处理，所以只需要递归右边的部分即可，此时从右边部分中寻找k减左边元素个数之后的剩余个数即可。

算法的平均时间复杂度为$O(n)$，空间复杂度为O(1)。

class Solution:
    def getLeastNumbers(self, arr, k):
        def quick_sort(arr, k, begin, end):
            if k != 0 or begin < end:
                pivot, head, tail = arr[begin], begin, end
                while head < tail:
                    while head < tail and arr[tail] > pivot:
                        tail -= 1
                    while head < tail and arr[head] <= pivot:
                        head += 1
                    arr[head], arr[tail] = arr[tail], arr[head]
                arr[begin], arr[tail] = arr[tail], arr[begin]
                if head - begin + 1 == k:
                    return
                elif head - begin + 1 > k:
                    quick_sort(arr, k, begin, head - 1)
                else:
                    quick_sort(arr, k - (head - begin + 1), head + 1, end)

        quick_sort(arr, k, 0, len(arr) - 1)
        return arr[:k]

刷题总结

这就是这道题目的三种解法，要面试的小伙伴们一定要记住后两种。快速排序看起来简单，但是一定要多写一写实现一下，千万不要出现差错，尽量一次成功。