4

[每天一道LeetCode] 面试题40. 最小的k个数

 2 years ago
source link: https://doumao.cc/index.php/%E7%BC%96%E7%A8%8B/%E6%AF%8F%E5%A4%A9%E4%B8%80%E9%81%93LeetCode-%E9%9D%A2%E8%AF%95%E9%A2%9840-%E6%9C%80%E5%B0%8F%E7%9A%84k%E4%B8%AA%E6%95%B0.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

[每天一道LeetCode] 面试题40. 最小的k个数

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

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
输入：arr = [0,1,2,1], k = 1
输出：[0]
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

一般看到求最小或者最大的k个数这种题目，会想到使用堆。题目要找出最小的k个数，那么我们可以维护一个最大堆。遍历一遍数组，如果堆中数字个数还不满k个，直接将当前数字入堆。否者，将当前数字和堆顶数字比较，如果当前数字<堆顶数字，将堆顶数字移出堆，当前数字入堆。

因为python标准库只有最小堆，要特殊处理下。

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k == 0:
            return []
        heap = []
        for num in arr:
            if len(heap) < k:
                heapq.heappush(heap, -num)
            else:
                if -num > heap[0]:
                    heapq.heappop(heap)
                    heapq.heappush(heap, -num)
        return [-num for num in heap]

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK