给定一个长度为N的数列,求有多少个区间满足区间中出现最多的数的个数大于等于K?c++代码
时间: 2024-01-22 14:18:19 浏览: 29
以下是C++代码实现:
```c++
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 1e5 + 5;
int n, k, a[MAXN];
int cnt[MAXN], maxn = 0, ans = 0;
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int l = 1, r = 1; r <= n; r++) {
cnt[a[r]]++;
maxn = max(maxn, cnt[a[r]]);
while (r - l + 1 - maxn >= k) {
cnt[a[l]]--;
l++;
for (int i = 1; i <= n; i++) {
maxn = max(maxn, cnt[i]);
}
}
ans += r - l + 1;
}
cout << ans << endl;
return 0;
}
```
算法思路:
使用双指针,变量 `maxn` 表示当前区间内出现次数最多的数的出现次数,变量 `cnt` 统计每个数出现的次数。
每当右指针移动时,更新 `cnt` 和 `maxn`,同时判断当前区间是否满足条件,如果不满足条件则将左指针向右移动,同时更新 `cnt` 和 `maxn` 直到区间满足条件。
更新答案时要加上当前区间的长度。