IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> leetcode825. 适龄的朋友 -> 正文阅读

[数据结构与算法]leetcode825. 适龄的朋友

在这里插入图片描述

LeetCode系列文章

一、题目描述

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

  • a g e s [ y ] ≤ 0.5 × a g e s [ x ] + 7 ages[y]\leq0.5\times ages[x]+7 ages[y]0.5×ages[x]+7
  • a g e s [ y ] > a g e s [ x ] ages[y]>ages[x] ages[y]>ages[x]
  • a g e s [ y ] > 100 & & a g e s [ x ] < 100 ages[y]>100\&\&ages[x]<100 ages[y]>100&&ages[x]<100

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

二、示例

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

三、主体思路

1、暴力解法

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

2、排序+双指针

??仔细观察题目所给的三个条件,你会发现条件三其实是蕴含在条件二当中的,如果满足了条件三那就一定满足条件二,因此只要不满足前两个条件,那么用户 x x x 就能向用户 y y y 发送好友请求,也就是用户 y y y 需要满足: 0.5 × a g e s [ x ] + 7 < a g e s [ y ] ≤ a g e s [ x ] 0.5\times ages[x]+7<ages[y]\leq ages[x] 0.5×ages[x]+7<ages[y]ages[x]
?
将这个关系用数轴表示如下:
在这里插入图片描述
??如果存在满足要求的用户 y y y,那么 0.5 × x + 7 < x 0.5\times x+7<x 0.5×x+7<x,即 x > 14 x > 14 x>14。也就是说,如果一个用户的年龄小于等于14,那么该用户将不能向任何用户发送好友请求。

??现在看来,要知道用户 x x x 能够向哪些用户 y y y 发送好友请求,实际就需要求出该数轴上对应的左右边界,年龄位于该区域内的用户就是用户 x x x 能够向其发送好友请求的用户。
?
??在寻找左右边界时可以用 l e f t left left r i g h t right right 表示左右边界的下标(双指针),如果左右都采用闭区间,即 l e f t left left 指向的是第一个满足要求的用户, r i g h t right right 指向的是最后一个满足要求的用户,那么最终 r i g h t ? l e f t right-left right?left 的值就是满足要求的用户 y y y 的个数。(注意:这里不是 r i g h t ? l e f t + 1 right-left+1 right?left+1,因为用户 x x x 本身也是在该区域当中的,但用户 x x x 不会向自己发送好友请求)
在这里插入图片描述
因此解题步骤如下:

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

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

3、计数排序+前缀和

??仔细观察你会发现题目给定用户的年龄是在 [ 1 , 120 ] [1, 120] [1,120] 范围内的,因此我们可以采用计数排序统计各个年龄段用户的个数并进行排序。
?
??比如我们将排序结果存储到 c n t cnt cnt 数组当中,此时 c n t [ a g e ] cnt[age] cnt[age] 就表示年龄为 a g e age age 的用户个数,而每一个年龄为 a g e age age 的用户能够向外发送的好友请求的数量就是: ( ∑ i = 0.5 × a g e + 8 a g e c n t [ i ] ) ? 1 (\sum_{i=0.5\times age+8}^{age}cnt[i])-1 (i=0.5×age+8age?cnt[i])?1,其中减一是因为用户不会向自己发送好友请求。
?
??为了避免每次都要遍历 c n t cnt cnt 数组进行求和,我们可以计算出 c n t cnt cnt 数组的前缀和数组 p r e pre pre p r e [ a g e ] pre[age] pre[age] 代表的就是年龄段位于1 ~ age的用户个数: p r e [ a g e ] = ∑ i = 1 a g e c n t [ i ] pre[age]=\sum_{i=1}^{age}cnt[i] pre[age]=i=1age?cnt[i]
?
??此时每一个年龄为 a g e age age 的用户能够向外发送的好友请求的数量就可以写为: p r e [ a g e ] ? p r e [ 0.5 × a g e + 7 ] ? 1 pre[age]-pre[0.5\times age+7]-1 pre[age]?pre[0.5×age+7]?1
在这里插入图片描述
??此时我们就能够在 O ( 1 ) O(1) O(1) 的时间内计算出一个年龄为 a g e age age 的用户能够向外发送的好友请求的数量,将该值乘以 c n t [ a g e ] cnt[age] cnt[age] 就是该年龄段的所有用户总计能够向外发送的好友请求的数量。

因此解题步骤如下:

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

四、代码实现

1、暴力解法

在这里插入图片描述

2、排序+双指针

在这里插入图片描述

3、计数排序+前缀和

在这里插入图片描述

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-07-04 23:13:18  更:2022-07-04 23:15:44 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/29 8:19:33-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计