每日一题-20

题目描述

最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

解题思路

1.利用快速排序的思想。快速排序每次会确定一个元素的位置，这个元素的左边都小于它，右边都大于它。快排源代码如下。

    def quick_sort(self, array, left, right):
        if left >= right:
            return
        low = left
        high = right
        key = array[low]
        while left < right:
            while left < right and array[right] > key:
                right -= 1
            array[left] = array[right]
            while left < right and array[left] <= key:
                left += 1
            array[right] = array[left]
        array[right] = key
        self.quick_sort(array, low, left - 1)
        self.quick_sort(array, left + 1, high)

而我们只需要判断这个元素的索引与k-1的大小关系。

• 若等于，则数组当前的前k个数即最小k，返回。
• 若大于，说明最小k在前半部分，所以继续快排前半部分。
• 若小于，说明最小k在后半部分，所以继续快排后半部分。

2.利用堆。
设置一个大小为K大根堆。
遍历整个数组：

• 若大根堆没有装满，则继续插入。
• 若大根堆已经装满，判断堆顶与新元素的大小
  若新元素大于堆顶元素，则继续遍历。
  若新元素小于堆顶元素，则将堆顶删除，然后把新元素插入到堆中。
• 最后整个堆存储的即最小k

3.hash表，空间换时间。首先找到数组中的最大值max，然后设置一个最大值+1的hash表。

• 遍历一次数组，查找1-max中每个数在数组中出现的次数。
• 遍历hash表，由于hash的键是有序的（1-max）,所以遇到次数大于0的，则把对应的键加到输出数组中。次数大于1的，键值相应的加几次。输出数组大小等于K,则退出。

代码

class Solution:
    def quick_K(self, arr, left, right, k):
        if left >= right:
            return
        low = left
        high = right
        key = arr[low]
        while left < right:
            while left < right and arr[right] > key:
                right -= 1
            arr[left] = arr[right]
            while left < right and arr[left] <= key:
                left += 1
            arr[right] = arr[left]
        arr[right] = key
        if right==k:
            return
        elif right<k:
            self.quick_K(arr, left + 1, high, k)
        else:
            self.quick_K(arr, low, left - 1, k)

    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        self.quick_K(arr, 0, len(arr)-1, k-1)
        return arr[:k]