825.适龄的朋友

【LetMeFly】825.适龄的朋友：双指针(排序nlog n) 或 桶排序(n + C^2)

力扣题目链接：https://leetcode.cn/problems/friends-of-appropriate-ages/

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。

如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：

• ages[y] <= 0.5 * ages[x] + 7
• ages[y] > ages[x]
• ages[y] > 100 && ages[x] < 100

否则，x 将会向 y 发送一条好友请求。

注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。

返回在该社交媒体网站上产生的好友请求总数。

 

示例 1：

输入：ages = [16,16]
输出：2
解释：2 人互发好友请求。

示例 2：

输入：ages = [16,17,18]
输出：2
解释：产生的好友请求为 17 -> 16 ，18 -> 17 。

示例 3：

输入：ages = [20,30,100,110,120]
输出：3
解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。

 

提示：

• n == ages.length
• 1 <= n <= 2 * 104
• 1 <= ages[i] <= 120

方法一：双指针

如果满足第三条ages[y] > 100 && ages[x] < 100，那么一定满足第二条ages[y] > ages[x]，因此第三条可以忽略（只要满足第二条，不需要看是否满足第三条就一定不会受到邀请）。

由第一条和第二条可知，当y满足0.5x+7 < y <= x时y才会收到来自x的邀请。由0.5x+7 < x可得只有>= 15的x才会有可能发送邀请。

对于邀请发送者x，y的最小值需要满足y > 0.5x+7，y的最大值需要满足y <= x。

假设y_l是第一个满足> 0.5x+7的y下标，y_r是最后一个满足<= x的y下标，那么对于区间[y_l, y_r]，只有x自身不会收到x的邀请，其他用户都会收到x的邀请。因此x的邀请发送数量为区间长度 - 1 = y_r - y_l。

不难发现随着x的非递减，y区间的左右端点y_l和y_r也是非递减的，因此就可以使用双指针来实现每个元素只被遍历数次。

• 时间复杂度$O(n\log n)$：排序时间复杂度$O(n\log n)$，双指针时间复杂度$O(n)$
• 空间复杂度$O(\log n)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2024-11-17 17:39:44
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2024-11-17 18:11:18
 */
/*
对于x：x要加：
0.5x+7 < y <= x
x + 7 < 2y
也就是说
0.5x+7 < x 可得 x>14 才能有朋友
*/
class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        int ans = 0;
        sort(ages.begin(), ages.end());
        int y_l = 0;
        while (y_l < ages.size() && ages[y_l] <= 14) {
            y_l++;
        }
        for (int y_r = y_l, x = y_l; x < ages.size(); x++) {
            while (ages[y_l] * 2 <= ages[x] + 14) {
                y_l++;
            }
            while (y_r + 1 < ages.size() && ages[y_r + 1] <= ages[x]) {
                y_r++;
            }
            ans += y_r - y_l;
        }
        return ans;
    }
};

方法二：桶排序

有没有一种办法避免方法一的时间瓶颈——排序呢？当然有。

不难发现每个人的年龄范围是1到120，因此我们只需要统计一下每个年龄段分别有多少人，再枚举x和y的年龄判定是否符合第一第二两个条件就好了。

• 时间复杂度$O(n + C^2)$：其中$C=120$
• 空间复杂度$O(C)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2021-12-27 09:00:07
 * @LastEditors: LetMeFly
 * @LastEditTime: 2021-12-27 09:07:32
 */
int a[121];
class Solution {
public:
    // age[y] * 2 <= age[x] + 14
    int numFriendRequests(vector<int>& ages) {
        for (int i = 0; i < 121; i++)
            a[i] = 0;
        for (int& t : ages)
            a[t]++;
        int ans = 0;
        for (int y = 1; y <= 120; y++) {
            for (int x = y; x <= 120; x++) {
                if (y * 2 <= x + 14 || (y > 100 && x < 100))
                    continue;
                ans += x == y ? a[x] * (a[x] - 1) : a[x] * a[y];
            }
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143836115