【双指针】适龄朋友
适龄朋友
在社交媒体网站上有 n 个用户。给你一个整数数组 ages ,其中 ages[i] 是第 i 个用户的年龄。
如果下述任意一个条件为真,那么用户 x 将不会向用户 y(x != y)发送好友请求:
- age[y] <= 0.5 * age[x] + 7
- age[y] > age[x]
- age[y] > 100 && age[x] < 100
否则,x 将会向 y 发送一条好友请求。
注意,如果 x 向 y 发送一条好友请求,y 不必也向 x 发送一条好友请求。另外,用户不会向自己发送好友请求。
返回在该社交媒体网站上产生的好友请求总数。
二分
最初的想法。条件三是条件二的充分条件,所以只用判断两种边界。
但实际上循环之中多次二分通常可以优化成双指针,因为循环中两个边界值都是递增的。
\(O(n\log n)\)。
class Solution {
public:
int numFriendRequests(vector<int>& ages) {
sort(ages.begin(), ages.end());
int ans = 0;
for (int i = 0; i < ages.size(); i++) {
int x = ages[i];
int lo = upper_bound(ages.begin(), ages.end(), floor(0.5 * x + 7)) - ages.begin();
// rule 3 --> rule 2
int hi = upper_bound(ages.begin(), ages.end(), x) - ages.begin();
ans += hi - lo - 1 > 0 ? hi - lo - 1 : 0; // must be positive
}
return ans;
}
};
双指针
\(O(n\log n)\),常数更低。
class Solution {
public:
int numFriendRequests(vector<int>& ages) {
int n = ages.size();
sort(ages.begin(), ages.end());
int left = 0, right = 0, ans = 0;
for (int age: ages) {
if (age < 15) continue;
while (ages[left] <= 0.5 * age + 7) ++left;
while (right + 1 < n && ages[right + 1] <= age) ++right;
ans += right - left;
}
return ans;
}
};
前缀和
由于年龄限制在120以内,更快的做法是暴力统计。
\(O(n)\)。
class Solution {
public:
int numFriendRequests(vector<int>& ages) {
vector<int> cnt(121);
for (int age: ages) ++cnt[age];
vector<int> pre(121);
for (int i = 1; i <= 120; ++i) pre[i] = pre[i - 1] + cnt[i];
int ans = 0;
for (int i = 15; i <= 120; ++i) {
if (cnt[i]) {
int bound = i * 0.5 + 8;
ans += cnt[i] * (pre[i] - pre[bound - 1] - 1);
}
}
return ans;
}
};