题目来源：Marscode。
小C和小U有一个从0开始的数组nums，以及一个非负整数k。每次操作中，小C可以选择一个尚未选择的下标i（范围在 [0, nums.length - 1]），然后将nums[i]替换为[nums[i] - k, nums[i] + k]之间的任意整数（包含边界）。在应用任意次数的操作后，返回数组nums可能达到的最大分数。数组的分数被定义为数组中最多重复的元素个数。注意，每个下标只能被操作一次。
暴力解（超时） O(n²k)# 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int solution(vector
int n = nums.size();
int maxCount = 1; // 至少有一个数
// 遍历每个数作为可能的目标值
for (int i = 0; i < n; i++) {
// 以nums[i]为中心，考虑范围[nums[i]-k, nums[i]+k]内的所有可能值
for (int target = nums[i]-k; target <= nums[i]+k; target++) {
int count = 0;
// 检查每个位置的数是否能变成target
for (int j = 0; j < n; j++) {
if (abs(nums[j] - target) <= k) {
count++;
}
}
maxCount = max(maxCount, count);
}
}
return maxCount;
}优化暴力解 O(n²)# 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int solution(vector
int n = nums.size();
int maxCount = 1;
// 只需要考虑将某些数变成数组中已有的数
for (int i = 0; i < n; i++) {
int target = nums[i]; // 以当前数作为目标值
int count = 0;
for (int j = 0; j < n; j++) {
if (abs(nums[j] - target) <= k) {
count++;
}
}
maxCount = max(maxCount, count);
}
return maxCount;
}扫描线算法 O(nlogn)#像是在数某个时刻有多少个区间重叠。一条水平线从左向右扫过，每个起点让重叠数+1，每个终点让重叠数-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
int solution(vector
int n = nums.size();
vector
// 计算每个数可以变化的范围
for (int i = 0; i < n; i++) {
ranges.push_back({nums[i] - k, 1}); // 范围起点
ranges.push_back({nums[i] + k + 1, -1}); // 范围终点
}
// 按照位置排序
sort(ranges.begin(), ranges.end());
int maxCount = 1;
int count = 0;
// 扫描线算法
for (const auto& range : ranges) {
count += range.second;
maxCount = max(maxCount, count);
}
return maxCount;
}注：std::sort 对 std::pair 的默认排序规则是：首先比较 first 成员，如果 first 相等，则比较 second 成员。
完整代码：
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
#include
#include
#include
using namespace std;
int solution(vector
int n = nums.size();
vector
// 计算每个数可以变化的范围
for (int i = 0; i < n; i++) {
ranges.push_back({nums[i] - k, 1}); // 范围起点
ranges.push_back({nums[i] + k + 1, -1}); // 范围终点
}
// 按照位置排序
sort(ranges.begin(), ranges.end());
int maxCount = 1;
int count = 0;
// 扫描线算法
for (const auto& range : ranges) {
count += range.second;
maxCount = max(maxCount, count);
}
return maxCount;
}
int main() {
vector
cout << (solution(nums1, 2) == 3) << endl;
vector
cout << (solution(nums2, 1) == 2) << endl;
vector
cout << (solution(nums3, 3) == 4) << endl;
return 0;
}