leetcode每日一题825. 适龄的朋友 快排+双指针

leetcode每日一题825. 适龄的朋友 快排+双指针

本文目录

• leetcode每日一题825. 适龄的朋友 快排+双指针
• • 写在前面
  • 题目
  • 示例
  • 提示
  • 思路
  • 代码实现
  • 执行结果
  • 写在后面

leetcode每日一题825. 适龄的朋友 快排+双指针 写在前面

又到了工作日的星期一了，坚持打卡leetcode的每日一题，“适龄的朋友？" ，话不多说，冲冲冲！

题目

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

提示

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

思路

快排 + 双指针的思想：
1)读题、从题中咱们可以知道 可以接受同龄的朋友 且比自己大一定范围内的朋友才可以接受好友请求。
2)先将所有年龄的人进行顺序排序，方便记录人数。
3)构建一个检查函数用来判定其两人是否会通过请求：

//如果通过此check则说明可以发送请求
 public boolean check(int x, int y) {
        if (y <= 0.5 * x + 7) return false;
        if (y > x) return false;
        if (y > 100 && x < 100) return false; 
        return true;
    }

4)根据双指针来定义区间：

• 指针 i 用来记录到达当前x年龄的第一个人的位置下标
• 指针 j 用来记录到达当前x年龄后能接受的最大年龄的人的位置下标

5)故此咱们可以得到：

• i 下标 < 当前人的位置 && 不满足交友条件时 i 指针后移直到找到第一个满足条件的人。
• j 下标 < 所有人数 && 满足条件时 j 指针后移 直到找到第一个不满足条件的人
• 随后求解

代码实现

class Solution {
    public int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        int ans = 0;
        //思路在这里
        for (int i =0,j=0,k=0;k i) ans += j - i - 1;
        }
        return ans;
    }
    //检查函数
    public boolean check(int x, int y) {
        if (y <= 0.5 * x + 7) return false;
        if (y > x) return false;
        if (y > 100 && x < 100) return false; 
        return true;
    }
}

执行结果

写在后面

今天是2021-12-27
坚持打卡每一天~
从小付做起

最后

每天进步点 每天收获点

愿诸君 事业有成 学有所获

如果觉得不错 别忘啦一键三连哦~