LeetCode每日一题-211227(825. 适龄的朋友)

LeetCode每日一题-21/12/27(825. 适龄的朋友)

825. 适龄的朋友

题目描述
适龄的朋友
在社交媒体网站上有 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 发送一条好友请求。另外，用户不会向自己发送好友请求。返回在该社交媒体网站上产生的好友请求总数。

• n == ages.length
• 1 <= n <= 2 * 10^4
• 1 <= ages[i] <= 120

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

题目分析
题目要求对符合要求的 y y y 发送请求，由题目可以知道需要 0.5 a g e [ x ] + 7 < a g e [ y ] ≤ a g e [ x ] 0.5age[x]+70.5age[x]+7 考虑到 y y y 在一个区间中，区间两端动态变化，则可以用双指针，因为涉及到年龄区间，所以我们需要对所有人的年龄先排序，排序时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)，遍历 x x x 及维护双指针的时间复杂度为 O ( n ) O(n) O(n)。
因为题目已给定ages的范围在[1,120]，范围不大，故可以使用桶排序或者计数排序将时间复杂度降到 O ( n + C ) O(n+C) O(n+C)，排序结束后由于每个桶中的人age都一样，要统计数量则通常采用前缀和数组， c o u n t + = ( p r e [ i ] − p r e [ ⌊ i ∗ 0.5 + 7 ] − 1 ⌋ ) ∗ c n t [ i ] count+=(pre[i] - pre[left lfloor i * 0.5 + 7] - 1 right rfloor) * cnt[i] count+=(pre[i]−pre[⌊i∗0.5+7]−1⌋)∗cnt[i]，其中向下取整可用 i n t int int 强制类型转换( i n t int int 是向 0 取整)。(桶数最大时桶排序退化为计数排序，计数排序常和前缀和数组一起使用，因为每个“桶”中的元素值都是一样的，统计数量时前缀和数组最为方便)
注：原题中说 x , y x,y x,y 不必互发请求的意思是若 x x x 满足 y y y 的条件而 y y y 不满足 x x x 的条件则他们之间只产生一个请求，如16，17，互相都满足好友条件时才产生两个请求，如16，16。

---

方法一 双指针

class Solution {
public:
    int numFriendRequests(vector& ages) {
        sort(ages.begin(), ages.end());
        int left = 0, right = 0, count = 0;
        for(int age: ages) {
            if(age < 15)continue;
            while(ages[left] <= 0.5 * age + 7)++left;
            while(right + 1 < ages.size() && ages[right + 1] <= age)++right;
            count += right - left;
        }
        return count;
    }
};

---

方法二 计数排序/桶排序+前缀和

class Solution {
public:
    int numFriendRequests(vector& ages) {
        vector cnt(121);
        for(int age: ages)++cnt[age];
        vector pre(121);
        for(int i = 1; i < 121; i++)pre[i] = pre[i - 1] + cnt[i];
        int count = 0;
        for(int i = 15; i < 121; i++){
            if(cnt[i]){
                int floor = i * 0.5 + 7;
                count += (pre[i] - pre[floor] - 1) * cnt[i];
            }
        }
        return count;
    }
};