leetcode825. 适龄的朋友

LeetCode系列文章

一、题目描述

  在社交媒体网站上有 $n$ 个用户。给你一个整数数组 $ages$，其中 $ages[i](1\le ages[i]\le 120)$ 是第 $i$ 个用户的年龄。
 
  如果下述任意一个条件为真，那么用户 $x$ 将不会向用户 $y$ 发送好友请求：

• $ages[y]\le 0.5\times ages[x]+7$
• $ages[y]>ages[x]$
• $ages[y]>100\&\&ages[x]<100$

  否则，$x$ 将会向 $y$ 发送一条好友请求。
 
  注意，如果 $x$ 向 $y$ 发送一条好友请求，$y$ 不必也向 $x$ 发送一条好友请求。另外，用户不会向自己发送好友请求。
 
  返回在该社交媒体网站上产生的好友请求总数。

二、示例

  输入： ages = [16, 16]
  输出： 2
 
  解释： 2人互发好友请求。

三、主体思路

1、暴力解法

  采用暴力解法解决该题目是非常简单的，要判断一个用户能够给哪些用户发送好友请求，只需要遍历这 $n-1$（不包括自己）个用户，依次判断是否满足发送好友请求的条件即可。
 
  很明显这种暴力解法的时间复杂度是 $O(N^2)$，当用户数据量过大时计算消耗的时间就会暴增，因此这种解法是不推荐的。

2、排序+双指针

  仔细观察题目所给的三个条件，你会发现条件三其实是蕴含在条件二当中的，如果满足了条件三那就一定满足条件二，因此只要不满足前两个条件，那么用户 $x$ 就能向用户 $y$ 发送好友请求，也就是用户 $y$ 需要满足：$0.5\times ages[x]+7<ages[y]\le ages[x]$
 
将这个关系用数轴表示如下：

  如果存在满足要求的用户 $y$，那么 $0.5\times x+7<x$，即 $x>14$。也就是说，如果一个用户的年龄小于等于14，那么该用户将不能向任何用户发送好友请求。

  现在看来，要知道用户 $x$ 能够向哪些用户 $y$ 发送好友请求，实际就需要求出该数轴上对应的左右边界，年龄位于该区域内的用户就是用户 $x$ 能够向其发送好友请求的用户。
 
  在寻找左右边界时可以用 $left$ 和 $right$ 表示左右边界的下标（双指针），如果左右都采用闭区间，即 $left$ 指向的是第一个满足要求的用户，$right$ 指向的是最后一个满足要求的用户，那么最终 $right-left$ 的值就是满足要求的用户 $y$ 的个数。（注意：这里不是 $right-left+1$，因为用户 $x$ 本身也是在该区域当中的，但用户 $x$ 不会向自己发送好友请求）

因此解题步骤如下：

• 对所给 $n$ 个用户的年龄进行排序。
• 依次遍历这 $n$ 个用户的年龄。
• 在遍历用户时，如果该用户的年龄小于等于14，则该用户能够向外发送好友请求的个数为0；如果该用户的年龄大于14，则通过双指针找到满足发送要求的区域，进而得出该用户能够向外发送的好友请求的个数。
• 最后将每个用户能够向外发送的好友请求的个数进行累加即可。

  特别注意，在通过双指针确定满足要求的年龄区域时，只有第一次需要在 $n$ 个用户的基础上从头进行查找。而后续在确定区域时，区域的左右边界只需要在上一个用户的左右边界的基础上向后进行查找即可。因为 $0.5\times x+7$ 与 $x$ 是线性的关系，当 $x$ 增大时，$0.5\times x+7$ 的值也会增大，因此我们无需再判断上一个用户的 $left$ 指针之前的用户年龄是否在本次限定的区域当中。

3、计数排序+前缀和

  仔细观察你会发现题目给定用户的年龄是在 $[1,120]$ 范围内的，因此我们可以采用计数排序统计各个年龄段用户的个数并进行排序。
 
  比如我们将排序结果存储到 $cnt$ 数组当中，此时 $cnt[age]$ 就表示年龄为 $age$ 的用户个数，而每一个年龄为 $age$ 的用户能够向外发送的好友请求的数量就是：$({\sum }_{i=0.5\times age+8}^{age}cnt[i])-1$，其中减一是因为用户不会向自己发送好友请求。
 
  为了避免每次都要遍历 $cnt$ 数组进行求和，我们可以计算出 $cnt$ 数组的前缀和数组 $pre$，$pre[age]$ 代表的就是年龄段位于1 ~ age的用户个数：$pre[age]={\sum }_{i=1}^{age}cnt[i]$。
 
  此时每一个年龄为 $age$ 的用户能够向外发送的好友请求的数量就可以写为：$pre[age]-pre[0.5\times age+7]-1$

  此时我们就能够在 $O(1)$ 的时间内计算出一个年龄为 $age$ 的用户能够向外发送的好友请求的数量，将该值乘以 $cnt[age]$ 就是该年龄段的所有用户总计能够向外发送的好友请求的数量。

因此解题步骤如下：

• 通过计数排序统计每个年龄段的用户个数。
• 计数出 $cnt$ 数组的前缀和数组 $pre$。
• 通过 $(pre[age]-pre[0.5\times age+7]-1)\times cnt[age]$ 公式计算出每个年龄段的用户总计能够向外发送的好友请求的数量，将其进行累加就是最终结果。

四、代码实现

1、暴力解法

2、排序+双指针

3、计数排序+前缀和