我只想到用 Counting Sort (O(n*exp[i]_range))。
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
| int activityNotifications(vector<int> e, int d) {
int ct=0;
vector<int> m(205,0);
for(int i=0;i<d;i++){
m[e[i]]++;
}
for(int i=d;i<e.size();i++){
int k=0,p=-1;
for(int j=0;j<201;j++){
k+=m[j];
if(d&1){
if(k>=d/2+1){
if(e[i]>=j*2) ct++;
break;
}
}else{
if(k==d/2){
p=j;
}else if(k>d/2){
if(p==-1){
if(e[i]>=j*2) ct++;
}else{
if(e[i]>=j+p) ct++;
}
break;
}
}
}
m[e[i]]++;
m[e[i-d]]--;
}
return ct;
}
|