0825. 适龄的朋友【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 计数

1. 📝 题目描述

• leetcode

在社交媒体网站上有 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 * 10^4
• 1 <= ages[i] <= 120

2. 🎯 s.1 - 计数

c

int numFriendRequests(int* ages, int agesSize) {
    int cnt[121] = {0};
    for (int i = 0; i < agesSize; i++) cnt[ages[i]]++;
    int res = 0;
    for (int a = 1; a <= 120; a++)
        for (int b = 1; b <= 120; b++) {
            if (2 * b <= a + 14) continue;
            if (b > a) continue;
            res += cnt[a] * (cnt[b] - (a == b ? 1 : 0));
        }
    return res;
}

js

/**
 * @param {number[]} ages
 * @return {number}
 */
var numFriendRequests = function (ages) {
  const cnt = new Array(121).fill(0)
  for (const a of ages) cnt[a]++
  let res = 0
  for (let a = 1; a <= 120; a++)
    for (let b = 1; b <= 120; b++) {
      if (b <= 0.5 * a + 7) continue
      if (b > a) continue
      res += cnt[a] * (cnt[b] - (a === b ? 1 : 0))
    }
  return res
}

py

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        cnt = [0] * 121
        for a in ages:
            cnt[a] += 1
        res = 0
        for a in range(1, 121):
            for b in range(1, 121):
                if b <= 0.5 * a + 7: continue
                if b > a: continue
                res += cnt[a] * (cnt[b] - (1 if a == b else 0))
        return res

• 时间复杂度：$O(n+A^2)$，其中 A = 120 是年龄范围
• 空间复杂度：$O(A)$

算法思路：

• 统计各年龄人数，枚举所有年龄对检查条件
• 条件：$b>0.5a+7$ 且 $b\le a$