最小的k个数（Python and C++解法）

题目：

输入整数数组 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]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof

思路：

　　方法一：可以借鉴快排的思想，将数组分成两个部分，小于等于分界值的元素的都会被放到数组的左边，大于的都会被放到数组的右边，然后返回分界值的下标，如果下标整好是k，那么左面的数据就是前k小的数，这种方法会改变原有的数组，时间复杂度是O（n）。

　　方法二：使用堆，但需要注意C++中默认大顶堆，Python默认小顶堆，时间复杂度是O（n*log k），这种方法适合海量数据。

Python解法：

 1 class Solution:
 2     def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
 3         res = []
 4         if k == 0:
 5             return res
 6         heap = []  # python默认是最小堆，因此需要将元素取反，维持最大的k个数
 7 
 8         for j in range(k):
 9             heapq.heappush(heap, -arr[j])  # 往堆中添加元素
10         for n in range(k, len(arr)):
11             if -arr[n] > heap[0]:  # 维持最大的K个数，那么相反数就是最小的k个数 
12                 heapq.heappop(heap)  # 弹出堆顶
13                 heapq.heappush(heap, -arr[n])
14         while heap:  # 当堆非空时
15             res.append(-heapq.heappop(heap))
16         return res

C++解法：

 1 class Solution {
 2 public:
 3     vector<int> getLeastNumbers(vector<int>& arr, int k) {
 4         vector<int> res;
 5         if(k == 0)
 6             return res;
 7         priority_queue<int> Queue;  // 声明优先级队列，C++默认是大顶堆
 8         for(int i = 0; i < k; i++)
 9             Queue.push(arr[i]);
10         for(int j = k; j < arr.size(); j++) {
11             if(arr[j] < Queue.top()) {  // 如果比堆顶小，则加入堆中,维持最小的K个数
12                 Queue.pop();
13                 Queue.push(arr[j]);
14             }
15         }
16         for(int i = 0; i < k; i++) {
17             res.push_back(Queue.top());
18             Queue.pop();
19         }
20         return res;
21     }
22 };