跳到主要内容

825.适龄的朋友

· 阅读需 5 分钟

1、题干​

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

2、题目分析​

  • 交友年龄限制的限制条件转换后，可以理解为：对于任意年龄ages[x]，交友范围的区间是(0.5 * ages[x] + 7,ages[x]]；
  • 由交友范围还可推断出，年龄15岁以下的用户交友范围区间是空集，因此后续编码时可以直接排除15岁以下的数据。

3、解法1-计数排序​

对年龄使用计数排序，遍历所有年龄age，累计并更新交友范围区间(0.5 * age + 7,age]内的人数preCount，然后对最终结果res累加当前年龄的交友请求数(preCount - 1) * counts[age]

4、代码​

var numFriendRequests = function (ages) {
    const counts = new Array(121).fill(0);
    for (const age of ages) if (age > 14) counts[age]++;
    let preCount = 0, res = 0;
    for (let age = 15; age < counts.length; age++) {
        if (age % 2 === 0) preCount -= counts[((age - 1) / 2 + 8) >> 0];
        preCount += counts[age];
        res += (preCount - 1) * counts[age];
    }
    return res;
};

代码简要说明

  • if (age % 2 === 0) preCount -= counts[((age - 1) / 2 + 8) >> 0]
    • 对于任意年龄age与age-1而言，交友年龄下限分别为counts[(age / 2 + 8) >> 0]、counts[((age - 1) / 2 + 8) >> 0]
    • age为奇数时这两个交友年龄下限相同，age为偶数时交友年龄下限比age-1大1
    • 因此age为偶数时，需要减去age-1的交友下限人数counts[((age - 1) / 2 + 8) >> 0]
  • preCount += counts[age]
    • 加上当前年龄用户的数量
  • res += (preCount - 1) * counts[age]
    • 当前年龄人数为counts[age]，他们会给交友范围内除自己外的所有人preCount - 1发请求
    • 因此有res += (preCount - 1) * counts[age]

5、执行结果​

1.png


6、解法2-二分查找​

先对所有年龄ages进行降序排序，然后遍历所有年龄，对当前年龄的交友年龄下限进行二分查找，累计所有交友请求数。其中，遇到相同年龄时直接跳过并累计其数量same，当年龄不再相同时对最终结果累加same * (same - 1)

该方法存在较多边界条件，处理不当很容易报错，不建议使用该方法实现

7、代码​

var numFriendRequests = function (ages) {
    ages.sort((a, b) => b - a);
    let same = 1;
    return ages.reduce((acc, cur, i) => {
        if (cur === ages[i + 1]) same++;
        if (cur <= 14 || (cur === ages[i + 1] && i !== ages.length - 1)) return acc;

        let l = i + 1, r = ages.length - 1;
        while (l < r) {
            const m = Math.floor((l + r) / 2);
            ages[m] <= cur / 2 + 7 ? (r = m - 1) : (l = m + 1);
        }

        acc += same * (same - 1 + Math.max(0, r - i - (ages[r] > cur / 2 + 7 ? 0 : 1)));
        return (same = 1), acc;
    }, 0);
};

8、执行结果​

执行用时：124 ms 内存消耗：47.3 MB