一、题目描述
输入整数数组 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
二、题解
解法一：排序
一个最简单的思路是先对所有元素排序，然后输出前面 k 个元素。使用快速排序的话，时间复杂度 O(nlog(n)) 。
解法二：时间复杂度为 O(n) 的快速排序
快速排序的特点是：每次排序后，标杆元素左边的元素都比它小，右边的元素都比它大。因此可以利用这一个特性，对数组中的元素进行部分排序，直到返回的标杆元素下标等于 k，那么这个标杆元素的左边就是所有需要的目标数据。
相较于快排来说，只需要对目标区间 （标杆元素左边或者右边） 进行排序就行了，无需对左右两边的区间都进行排序。因此时间复杂度降为 O(n) 。
解法三：最大堆
最大堆的性质是：堆上层的元素都大于等于下层元素。因此，只要维护一个大小为 k 的最大堆，循环遍历数组，如果元素大于堆顶元素，就替换掉堆顶元素，重新建堆。堆里面保存的就是 k 个最小的元素了。时间复杂度 O(nlog(k))，空间复杂度 O(k) 。
三、代码：
3.1 基于快排思想的算法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
class Solution { private: int partition(vector<int> &arr, int left, int right) { int i, j, key; if (left >= right) return left; i = left; j = right; key = arr[i]; while (i < j) { while (i < j && arr[j] >= key) { j--; } if (i < j && arr[j] < key) { arr[i] = arr[j]; } while (i < j && arr[i] <= key) { i++; } if (i < j && arr[i] > key) { arr[j] = arr[i]; } } arr[i] = key; return i; } public: vector<int> getLeastNumbers(vector<int> &arr, int k) { int idx, left, right; vector<int> output; if (arr.size() <= k) return arr; if (arr.size() == 0) return output; left = 0; right = arr.size() - 1; // 循环分区，找到第 k 个标杆元素 idx = partition(arr, left, right); while (idx != k) { if (idx > k) { // 标杆元素的下标大于 k，要在左区间继续找 right = idx - 1; idx = partition(arr, left, right); } else { // 标杆元素的下标小于 k，要在右区间继续找 left = idx + 1; idx = partition(arr, left, right); } } // 预分配空间，不要直接 push_back，否则会浪费很多重新开辟空间的时间 output.reserve(k); for (idx = 0; idx < k; idx++) { output.push_back(arr[idx]); } return output; } }; |
3.2 使用最大堆
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
class Solution { private: // 执行最大堆化 void maxHeapify(vector<int> &v, int idx) { int mid, i, left, right, largest; left = (idx * 2) + 1; right = left + 1; if (left < v.size() && v[left] > v[idx]) largest = left; else largest = idx; if (right < v.size() && v[right] > v[largest]) largest = right; if (largest != idx) { swap(v[largest], v[idx]); maxHeapify(v, largest); } } public: vector<int> getLeastNumbers(vector<int> &arr, int k) { int i, j, len; vector<int> output; if (k >= arr.size()) return arr; if (k == 0) return output; len = 0; output.reserve(k); for (i = 0; i < arr.size(); i++) { if (len < k) { // 当最大堆的元素个数小于 k 时，直接插入到堆 output.push_back(arr[i]); len++; // 堆塞满后，构造最大堆 if (len == k) { for (j = k / 2; j >= 0; j--) { maxHeapify(output, j); } } } else { // 元素小于堆顶元素，替换掉首元素 if (arr[i] < output[0]) { output[0] = arr[i]; maxHeapify(output, 0); } } } return output; } }; |
