每日一题——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 发送一条好友请求。另外，用户不会向自己发送好友请求。

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

---

早上被这种阅读理解题整的我有点爆炸

主要关键是我不能理解第一个用例

输入：

ages = [16,16]

输出：

2

解释：

2 人互发好友请求。

那你为什么还在题目中特别强调了这是互发是不必要的呢

所以这就是所谓的不必要吗？

把我整麻了

姑且还是放一下我的错误做法吧

public class Solution {
    public int NumFriendRequests(int[] ages) {
        Array.Sort(ages);
        int left = 0;
        int right = ages.Length-1;
        int ans = 0;
        while(left <= right)
        {
            if(left == right)
            {
                left++;
                right = ages.Length-1;
                continue;
            }

            if(ages[left] > 100 && ages[right] < 100)
            {
                right--;
            }
            else if(ages[left] <= (ages[right]*0.5 + 7))
            {
                right--;
            }
            else
            {
                ans++;
                if(ages[left] == ages[right])
                {
                    ans++;
                }
                right--;
            }

        }

        return ans;
    }
}

我的思路也是二分 但是我是用计数的方式的

所以遇到像这种极端用例又超时了

唉

贴贴官方题解的思路吧

思路差距在于

提炼条件可得0.5×ages[x]+7<ages[y]≤ages[x]

只需要 考虑年龄大于15的情况

x 发送的好友请求数，即为 [left,right] 区间的长度减去 1

将每一个 x 对应的[left,right] 区间长度减去 1 进行累加

就可以得到最终的答案

public class Solution {
    public int NumFriendRequests(int[] ages) {
        int n = ages.Length;
        Array.Sort(ages);
        int left = 0, right = 0, ans = 0;
        foreach (int age in ages) {
            if (age < 15) {
                continue;
            }
            while (ages[left] <= 0.5 * age + 7) {
                ++left;
            }
            while (right + 1 < n && ages[right + 1] <= age) {
                ++right;
            }
            ans += right - left;
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/friends-of-appropriate-ages/solution/gua-ling-de-peng-you-by-leetcode-solutio-v7yk/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。