给定一个长度为N的数列,求有多少个区间满足区间中出现最多的数的个数大于等于K?c++代码
时间: 2024-01-22 20:17:53 浏览: 49
以下是基于滑动窗口的双指针算法,时间复杂度为O(N)。
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
vector<int> count(100001, 0); // 统计每个数字出现的次数
int left = 0, right = 0, maxCount = 0, ans = 0;
while (right < n) {
maxCount = max(maxCount, ++count[nums[right]]);
while (right - left + 1 > maxCount + k) { // 如果区间长度大于最多数的个数+K,则左指针向右移动
--count[nums[left]];
++left;
maxCount = 0;
for (int i = left; i <= right; ++i) {
maxCount = max(maxCount, count[nums[i]]);
}
}
ans += (right - left + 1);
++right;
}
cout << ans << endl;
return 0;
}
```