LeetCode 2653 滑动子数组的美丽值
🟡中等
关键在于如何找到 topk的值。
可以使用 hash_map 来解决
class Solution {
public:
int get_k(unordered_map<int,int>& hash_map, int k){
int sum = 0;
for(int i = -50;i<0;i++){
if(hash_map[i]>0){
sum+=hash_map[i];
if(sum>=k){
return i;
}
}
}
return 0;
}
vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
unordered_map<int,int> hash_map;
for(int i =0;i<k-1;i++){
hash_map[nums[i]]++;
}
// int beauty = get_k(hash_map,x);
vector<int> res;
// res.push_back(beauty);
for(int i = k-1;i<nums.size();i++){
hash_map[nums[i]]++;
// if(hash_map[nums[i-k]]==0){
// hash_map.erase(nums[i-k]);
// }
res.push_back(get_k(hash_map,x));
hash_map[nums[i-k+1]]--;
}
return res;
}
};
优化后的版本
作个映射，-50-50映射到 0-100 ，不用 hash_map 存值， 直接使用数组即可。
class Solution {
public:
vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
int count[101];
for(int i =0;i<k-1;i++){
count[nums[i]+50]++;
}
vector<int> res;
for(int i = k-1;i<nums.size();i++){
count[nums[i]+50]++;
int rr = 0;
int sum = 0;
for(int j = -50;j<0;j++){
sum+=count[j+50];
if(sum>=x) {
rr = j;
break;
}
}
res.push_back(rr);
count[nums[i-k+1]+50]--;
}
return res;
}
};