用map记录数组,在数组中查询,从而保证时间复杂度在$O(NlogN)$
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
using namespace std;
const int N = 50010;
int lis[N];
int main(){
int n, k;
int ans = 0;
cin >> n >> k;
map<int, vector<int>> mp;
for(int i = 0;i < n;i ++){
int t;
cin >> t;
mp[t].push_back(i);
}
for(auto [key, v] : mp){
for(int i = 0;i < v.size() - 1;i ++){
if(v[i + 1] - v[i] <= k)
ans = max(ans, key);
}
}
if(ans)cout << ans;
else cout << -1;
}
增加一种标记法
实测快了一倍(
大佬们牛逼
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
using namespace std;
const int N = 1e6 + 10;
int lis[N];
bool mark[N];
int main(){
int n, k;
int ans = 0;
cin >> n >> k;
for(int i = 0;i < n;i ++){
int t;
cin >> t;
if(mark[t])
if(i - lis[t]<= k) {
ans = max(ans, t);
}
mark[t] = true;
lis[t] = i;
}
if(ans) cout << ans;
else cout << -1;
}
你的第二种方法好像过不了哦 比如这个示例都过不了6 3
7
2
3
7
2
3
今天新加的数据,被卡掉了,昨天还可以过掉的,数组多开一个用来标记
明白!