【双指针】适龄朋友

适龄朋友

在社交媒体网站上有 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;
    }
};