2021.12.27LeetCode每日一题——适龄的朋友

2021.12.27LeetCode每日一题——适龄的朋友,第1张

2021.12.27LeetCode每日一题——适龄的朋友

目录

适龄的朋友

描述

示例 1

示例 2

示例 3

提示

方法:排序+双指针


适龄的朋友 描述

在社交媒体网站上有 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 发送一条好友请求。另外,用户不会向自己发送好友请求。

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

示例 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 。
提示

方法:排序+双指针

由题目的三个条件可知,

  1. age[y] <= 0.5 * age[x] + 7
  2. age[y] > age[x]
  3. age[y] > 100 && age[x] < 100

条件 3 是包含在条件 2 中的,即如果满足条件 3 那么一定满足条件 2。因此,我们当条件 1 和 2 均不满足时,用户 x 就会向用户 y 发送好友请求,也就是用户 y 需要满足:

当 ages[x]≤14 时,不存在满足要求的 ages[y]。因此我们只需要考虑 ages[x]≥15 的情况,此时满足要求的 ages[y] 的范围为 (0.5×ages[x]+7,ages[x]]。

当 ages[x] 增加时,上述区间的左右边界均单调递增,因此如果我们将数组 ages 进行升序排序,那么就可以在遍历 ages[x] 的同时,使用两个指针 left 和 right 维护满足要求的 ages[y] 的左右边界。当 x 向后移动一个位置时:

  • 如果左边界指针 left 指向的元素不满足 ages[left]>0.5×ages[x]+7,那么就将左边界向后移动一个位置;
  • 如果右边界指针 right 指向的下一个元素满足 ages[right+1]≤ages[x],那么就将右边界向后移动一个位置。

这样一来,[left,right] 就是满足年龄要求的 y 的下标。需要注意的是,x 本身一定在[left,right] 区间内,因此 x 发送的好友请求数,即为 [left,right] 区间的长度减去 1。

我们将每一个 x 对应的 [left,right] 区间长度减去 1 进行累加,就可以得到最终的答案。

class Solution {
    public int numFriendRequests(int[] ages) {
        int n = ages.length;
        Arrays.sort(ages);
        int left = 0, right = 0, ans = 0;
        for (int age : 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;
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5682085.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存