日志统计 c++ unordered_map解题 滑动窗口

解题思路:map中键存储id 值存储时间,将所有的信息录入后对时间进行从小到大排序.遍历map,创建两个指针i=0,j=k-1,代表维护的滑动窗口的大小为k,当j指向的元素减去i指向的元素的结果小于等于D时,说明该id满足要求,否则i++,j++即窗口向右滑动1位.

注意事项:由于unordered_map并不会按顺序存储id,因此找到符合要求的id时存入set容器.然后遍历输出set容器元素.

参考代码:

#include <bits/stdc++.h>
typedef long long ll;
#define f first
#define s second
using namespace std;
int main(){
	unordered_map<ll,vector<int>> map;
	ll n,d,k,t,id;
	set<ll> res;
	cin>>n>>d>>k;
	for(int i=0;i<n;i++){
		scanf("%lld %lld",&t,&id);
		map[id].emplace_back(t);
	}
	ll len=map.size(),i,j;
	for(auto x:map){
		i=0,j=k-1;
		sort(x.s.begin(),x.s.end());
		while(j<x.s.size()){
			if((x.s[j]-x.s[i]+1)<=d){
				res.insert(x.f);
				break;
			}
			i++,j++;
		}
	}
	for(auto f:res)printf("%lld \n",f);
	return 0;
}