TopK問題
輸入陣列arr，找出其中最大的k個數，例如，輸入4、5、1、6、2、7、3、8這8個數字，則最大的4個數字是5、6、7、8，
示例一：
輸入：arr = [3,2,1], k = 2
輸出：[3,2]或者[2,3]
示例二：
輸入：arr = [0,1,2,1], k = 1
輸出：[2]
解題思路：
1.先把陣列中前K個資料，建成大堆
2.然后剩下的N-K個數，跟堆頂的資料比較，如果比堆頂的資料小，則替換堆頂的資料，調堆，
3.最后堆里面的就是最小的K個數
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int> vec(k, 0);
if (k == 0)
{
return vec;
}
priority_queue<int> Q;
for (int i = 0; i < k; ++i)
{
Q.push(arr[i]);
}
for (int i = k; i < (int)arr.size(); ++i)
{
if (Q.top() > arr[i]) {
Q.pop();
Q.push(arr[i]);
}
}
for (int i = 0; i < k; ++i)
{
vec[i] = Q.top();
Q.pop();
}
return vec;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/306280.html
標籤：其他