每日算法系列【LeetCode 825】适龄的朋友

题目描述

人们会互相发送好友请求，现在给定一个包含有他们年龄的数组，ages[i] 表示第 i 个人的年龄。

当满足以下条件时，A 不能给 B（A、B不为同一人）发送好友请求：

• age[B] <= 0.5 * age[A] + 7
• age[B] > age[A]
• age[B] > 100 && age[A] < 100

否则，A 可以给 B 发送好友请求。

注意如果 A 向 B 发出了请求，不等于 B 也一定会向 A 发出请求。而且，人们不会给自己发送好友请求。

求总共会发出多少份好友请求?

示例1

输入：
[16,16]
输出：
2
解释
二人可以互发好友申请。

示例2

输入：
[16,17,18]
输出：
2
解释：
好友请求可产生于 17 -> 16, 18 -> 17.

示例3

输入：
[20,30,100,110,120]
输出：
3
解释：
好友请求可产生于 110 -> 100, 120 -> 110, 120 -> 100.

提示

• 1 <= ages.length <= 20000.
• 1 <= ages[i] <= 120.

题解

暴力法

这题最暴力的方法显然就是遍历任意数对 a 和 b ，看两个数是否符合这个条件，但是时间复杂度太高，不可行。

二分法

计数法

代码

c++

classSolution {
public:
intnumFriendRequests(vector<int>&ages) { 
constintMA=120;
vector<int>count(MA+1, 0), sum(MA+1, 0);
intn=ages.size(), res=0;
for (inti=0; i<n; ++i) {
count[ages[i]]++;
            }
for (inti=1; i<=MA; ++i) {
sum[i] =sum[i-1] +count[i];
            }
for (intb=15; b<=MA; ++b) {
res+=count[b] * (sum[min(MA, 2*b-15)] -sum[b-1] -1);
            }
returnres;
        }};

python

classSolution: 
defnumFriendRequests(self, ages: List[int]) ->int:
MA=120count, S= [0]*(MA+1), [0]*(MA+1)
n, res=len(ages), 0forageinages:
count[age] +=1foriinrange(1, MA+1):
S[i] =S[i-1] +count[i] 
forbinrange(15, MA+1):
res+=count[b] * (S[min(MA, 2*b-15)] -S[b-1] -1)
returnres

作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~