题目描述
适龄的朋友
在社交媒体网站上有 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 发送一条好友请求。另外，用户不会向自己发送好友请求。返回在该社交媒体网站上产生的好友请求总数。
- n == ages.length
- 1 <= n <= 2 * 10^4
- 1 <= ages[i] <= 120
输入：ages = [20,30,100,110,120]
输出：3
解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。
题目分析
题目要求对符合要求的
y
y
y 发送请求，由题目可以知道需要
0.5
a
g
e
[
x
]
+
7
<
a
g
e
[
y
]
≤
a
g
e
[
x
]
0.5age[x]+70.5age[x]+7
因为题目已给定ages的范围在[1,120]，范围不大，故可以使用桶排序或者计数排序将时间复杂度降到
O
(
n
+
C
)
O(n+C)
O(n+C)，排序结束后由于每个桶中的人age都一样，要统计数量则通常采用前缀和数组，
c
o
u
n
t
+
=
(
p
r
e
[
i
]
−
p
r
e
[
⌊
i
∗
0.5
+
7
]
−
1
⌋
)
∗
c
n
t
[
i
]
count+=(pre[i] - pre[left lfloor i * 0.5 + 7] - 1 right rfloor) * cnt[i]
count+=(pre[i]−pre[⌊i∗0.5+7]−1⌋)∗cnt[i]，其中向下取整可用
i
n
t
int
int 强制类型转换(
i
n
t
int
int 是向 0 取整)。(桶数最大时桶排序退化为计数排序，计数排序常和前缀和数组一起使用，因为每个“桶”中的元素值都是一样的，统计数量时前缀和数组最为方便)
注：原题中说
x
,
y
x,y
x,y 不必互发请求的意思是若
x
x
x 满足
y
y
y 的条件而
y
y
y 不满足
x
x
x 的条件则他们之间只产生一个请求，如16，17，互相都满足好友条件时才产生两个请求，如16，16。
方法一 双指针
class Solution {
public:
int numFriendRequests(vector& ages) {
sort(ages.begin(), ages.end());
int left = 0, right = 0, count = 0;
for(int age: ages) {
if(age < 15)continue;
while(ages[left] <= 0.5 * age + 7)++left;
while(right + 1 < ages.size() && ages[right + 1] <= age)++right;
count += right - left;
}
return count;
}
};
方法二 计数排序/桶排序+前缀和
class Solution {
public:
int numFriendRequests(vector& ages) {
vector cnt(121);
for(int age: ages)++cnt[age];
vector pre(121);
for(int i = 1; i < 121; i++)pre[i] = pre[i - 1] + cnt[i];
int count = 0;
for(int i = 15; i < 121; i++){
if(cnt[i]){
int floor = i * 0.5 + 7;
count += (pre[i] - pre[floor] - 1) * cnt[i];
}
}
return count;
}
};
