共计 1342 个字符,预计需要花费 4 分钟才能阅读完成。
title: 每日一练(21):最小的 k 个数
categories:[剑指 offer]
tags:[每日一练]
date: 2022/02/17
每日一练(21):最小的 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
起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…
办法一:sort 排序
思路和算法
对原数组从小到大排序后取出前 k 个数即可。
复杂度剖析
- 工夫复杂度:O(n logn),其中 n 是数组 arr 的长度。算法的工夫复杂度即排序的工夫复杂度。
- 空间复杂度:O(logn),排序所需额定的空间复杂度为 O(logn)。
vector<int> getLeastNumbers(vector<int>& arr, int k) {vector<int> ans(k, 0);
if (arr.size() == 0 || k == 0) {return ans;}
sort(arr.begin(), arr.end()); // 排序
for (int i = 0; i < k; i++) {ans.push_back(arr[i]); // 增加到指标 vector
}
return ans;
}
办法二:堆
思路和算法
咱们用一个大根堆实时保护数组的前 k 小值。首先将前 k 个数插入大根堆中,随后从第 k+1 个数开始遍历,如果以后遍历到的数比大根堆的堆顶的数要小,就把
堆顶的数弹出,再插入以后遍历到的数。最初将大根堆里的数存入数组返回即可。在上面的代码中,因为 C++ 语言中的堆(即优先队列)为大根堆,咱们能够这
么做。而 Python 语言中的堆为小根堆,因而咱们要对数组中所有的数取其相反数,能力应用小根堆保护前 k 小值。
复杂度剖析
- 工夫复杂度:O(n logk),其中 nn 是数组 arr 的长度。因为大根堆实时保护前 k 小值,所以插入删除都是 O(logk) 的工夫复杂度,最坏状况下数组里 n 个数都会插入,所以一共须要 O(nlogk) 的工夫复杂度。
- 空间复杂度:O(k),因为大根堆里最多 k 个数。
vector<int> getLeastNumbers(vector<int>& arr, int k) {vector<int> ans(k, 0);
if (arr.size() == 0 || k == 0) {return ans;}
priority_queue<int> q;
for (int i = 0; i < k; ++i) { // 将前 k 个数插入堆中
q.push(arr[i]);
}
for (int i = 0; i < (int)arr.size(); ++i) {if (q.top() > arr[i]) { // 第 k+1 个数开始遍历,如果以后遍历到的数比大根堆的堆顶的数要小,就把
q.pop(); // 堆顶的数弹出,再插入以后遍历到的数
q.push(arr[i]);
}
}
for (int i = 0; i < k; ++i) {ans[i] = q.top(); // 把堆中的数存到指标 vector 中
q.pop();}
return ans;
}
正文完