题目描述

人们会互相发送好友请求，现在给定一个包含有他们年龄的数组，ages[i] 表示第 i 个人的年龄。

当满足以下条件时，A 不能给 B（A、B不为同一人）发送好友请求：

• age[B] <= 0.5 * age[A] + 7
• age[B] > age[A]
• age[B] > 100 && age[A] < 100

否则，A 可以给 B 发送好友请求。

注意如果 A 向 B 发出了请求，不等于 B 接受了 A 的请求。而且，人们不会给自己发送好友请求。

求总共会发出多少份好友请求?

样例

输入: [16,16]
输出: 2
解释: 二人可以互发好友申请。

输入: [16,17,18]
输出: 2
解释: 好友请求可产生于 17 -> 16, 18 -> 17.

输入: [20,30,100,110,120]
输出: 3
解释: 好友请求可产生于 110 -> 100, 120 -> 110, 120 -> 100.

注意

• 1 <= ages.length <= 20000.
• 1 <= ages[i] <= 120.

算法1

(排序) $O(n \log n)$

1. 将年龄数组从小到大排序。（条件 3 是没有用的。）
2. 然后算法分为两步，第一步是处理年龄相同的人的请求数；第二步是年龄不同的人的请求数。
3. 第一步只需要扫一遍数组，就可以知道每个年龄相同的人数有多少，如果年龄大于等于 15，则答案加 cnt * (cnt - 1)，cnt 表示这个年龄有多少个人。
4. 第二步时，同样扫一遍数组，维护两个指针 i 和 j，区间 j 到 i-1 里的所有人都是合法的，且年龄相同的人之间的请求不能重复计算。注意这里对年龄相同的人需要累加上同样的答案，代码中的 last 就是负责做这件事情。

时间复杂度

• 排序后扫两遍数组，故时间复杂度为 $O(n \log n)$。

空间复杂度

• 只需要常数的额外空间，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        int n = ages.size(), tot = 0, cnt = 1;
        sort(ages.begin(), ages.end());
        for (int i = 0; i < n; i++) {
            if (i == 0 || ages[i] > ages[i - 1]) {
                if (i > 0 && ages[i - 1] >= 15) {
                    tot += cnt * (cnt - 1);
                }
                cnt = 1;
            } else {
                cnt++;
            }
        }
        if (ages[n - 1] >= 15) {
            tot += cnt * (cnt - 1);
        }

        int last = 0;
        for (int i = 0, j = 0; i < n; i++) {
            if (i == 0 || ages[i] > ages[i - 1]) {
                while (j < i && (2 * (ages[j] - 7) <= ages[i] || ages[j] == ages[i]))
                    j++;
                tot += i - j;
                last = i - j;
            } else {
                tot += last;
            }
        }

        return tot;
    }
};

算法2

(统计) $O(n + A)$

1. 统计出每个年龄有多少人。
2. 扫描所有年龄，同时维护两个指针，类似于算法 1 统计答案。代码中的 sum 是年龄人数的前缀和。

时间复杂度

• 扫描一遍原数组，扫描一遍所有年龄，故时间复杂度为 $O(n + A)$。

空间复杂度

• 需要额外的空间记录每个年龄有多少人，故空间复杂度为 $O(A)$。

C++ 代码

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        int n = ages.size(), tot = 0;
        vector<int> cnt(121, 0), sum(121, 0);

        for (int i = 0; i < n; i++) {
            cnt[ages[i]]++;
        }
        sum[0] = cnt[0];
        for (int i = 1; i <= 120; i++)
            sum[i] = sum[i - 1] + cnt[i];

        for (int i = 0, j = 0; i <= 120; i++) {
            while (j < i && 2 * (j - 7) <= i)
                j++;

            if (i >= 15) {
                tot += cnt[i] * (cnt[i] - 1);
            }
            if (i > 0) {
                if (j > 0)
                    tot += cnt[i] * (sum[i - 1] - sum[j - 1]);
                else
                    tot += cnt[i] * sum[i - 1];
            }
        }

        return tot;
    }
};