剑指offer40.最小的k个数

**剑指Offer40: 最小的 k 个数**

### 题目描述输入一个长度为 n 的整型数组和一个整型 k。请返回长度为 k 的子数组中最小的 k 个数字。如果不存在长度为 k 的子数组，则输出原数组中最小的 k 个数字。

### 示例1:

输入: arr = [4,5,5,9], k =3输出: [1,4,5]

### 示例2:

输入: arr = [1,2,3,4,5,6,7,8,9], k =10输出: [1,2,3,4,5,6,7,8,9]

### 解决方案#### 方法一：使用堆栈实现我们可以使用一个最大堆来存储最小的 k 个数字。每次插入新数字时，我们都需要检查堆中是否有大于该数字的元素，如果有，则将其弹出并放入新数字。

import heapqclass Solution:
 def GetLeastKNumber(self, arr, k):
 # 使用最大堆存储最小的 k 个数字 max_heap = []
 for num in arr:
 # 将新数字插入堆中 heapq.heappush(max_heap, -num)
 # 如果堆中元素超过 k 个，则弹出最大的元素 if len(max_heap) > k:
 heapq.heappop(max_heap)
 # 返回堆中的最小 k 个数字 return [-num for num in max_heap]

class Solution:
 def GetLeastKNumber(self, arr, k):
 # 使用快速排序算法找到原数组中最小的 k 个数字 sorted_arr = self.quick_sort(arr)
 return sorted_arr[:k]
 def quick_sort(self, arr):
 if len(arr) <=1:
 return arr pivot = arr[len(arr) //2]
 left = [x for x in arr if x < pivot]
 middle = [x for x in arr if x == pivot]
 right = [x for x in arr if x > pivot]
 return self.quick_sort(left) + middle + self.quick_sort(right)