给你一个下标从 0 开始的整数数组 nums 和一个 非负 整数 k 。 在一步操作中,你可以执行下述指令: 在范围 [0, nums.length - 1] 中选择一个 此前没有选过 的下标 i 。 将 nums[i] 替换为范围 [nums[i] - k, nums[i] + k] 内的任一整数。 数组的 美丽值 定义为数组中由相等元素组成的最长子序列的长度。 对数组 nums 执行上述操作任意次后,返回数组可能取得的 最大 美丽值。 注意:你 只 能对每个下标执行 一次 此操作。 数组的 子序列 定义是:经由原数组删除一些元素(也可能不删除)得到的一个新数组,且在此过程中剩余元素的顺序不发生改变。1 <= nums.length <= 10的5次方, 0 <= nums[i], k <= 10的5次方。用c++代码来解决
时间: 2024-04-18 21:23:37 浏览: 95
下面是使用 C++ 解决该问题的代码:
```cpp
#include <vector>
#include <unordered_map>
#include <algorithm>
int maximumBeauty(std::vector<int>& nums, int k) {
int n = nums.size();
std::unordered_map<int, int> freq;
int max_beauty = 0;
for (int i = 0; i < n; i++) {
freq[nums[i]]++;
}
for (int i = 0; i < n; i++) {
int curr_beauty = 0;
if (freq[nums[i]] > 1) {
curr_beauty = freq[nums[i]];
} else {
for (int j = std::max(0, nums[i] - k); j <= std::min(nums[i] + k, 100000); j++) {
if (freq[j] > 0) {
curr_beauty = freq[j];
}
}
}
max_beauty = std::max(max_beauty, curr_beauty);
}
return max_beauty;
}
```
需要注意的是,代码中使用了 `unordered_map` 来统计每个元素的出现次数。由于题目中给定了元素的范围为 0 到 10^5,因此我们可以使用数组来代替 `unordered_map` 来提高效率。
希望能帮到你!如果还有其他问题,请随时提问。
阅读全文