Medium
题目描述
在社交媒体网站上有 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
解释：两个 16 岁的用户会互相发送好友请求。
示例 2：
输入：ages = [16,17,18]
输出：2
解释：好友请求为 17 -> 16, 18 -> 17。
示例 3：
输入：ages = [20,30,100,110,120]
输出：3
解释：好友请求为 110 -> 100, 120 -> 110, 120 -> 100。
提示：
- n == ages.length
- 1 <= n <= 2 * 10^4
- 1 <= ages[i] <= 120
解题思路
解题思路
首先分析好友请求的条件。用户 x 向用户 y 发送好友请求的条件是：
- age[y] > 0.5 * age[x] + 7
- age[y] <= age[x]
- 不满足 age[y] > 100 && age[x] < 100（即 age[y] <= 100 或 age[x] >= 100）
可以简化为：当 0.5 * age[x] + 7 < age[y] <= age[x] 且不违反第三个条件时，x 会向 y 发送请求。
方法一：暴力遍历 直接双重循环检查每对用户，时间复杂度 O(n²)。
方法二：排序+双指针（推荐） 由于年龄范围有限（1-120），可以统计每个年龄的人数，然后对于每个年龄 x，计算有多少个年龄 y 满足条件。排序后使用双指针或二分查找确定满足条件的年龄范围，大大减少计算量。
具体步骤：
- 统计每个年龄的人数
- 对于每个年龄 x，计算满足条件的年龄范围 [left, right]
- 计算该年龄段的总人数，乘以年龄为 x 的人数
- 特别处理相同年龄的情况（count[x] * (count[x] - 1)）
这种方法时间复杂度为 O(A²)，其中 A 是年龄的取值范围（120），比 O(n²) 要高效很多。
代码实现
class Solution {
public:
int numFriendRequests(vector<int>& ages) {
vector<int> count(121, 0);
for (int age : ages) {
count[age]++;
}
int result = 0;
for (int ageX = 1; ageX <= 120; ageX++) {
if (count[ageX] == 0) continue;
for (int ageY = 1; ageY <= 120; ageY++) {
if (count[ageY] == 0) continue;
// Check conditions
if (ageY <= 0.5 * ageX + 7) continue;
if (ageY > ageX) continue;
if (ageY > 100 && ageX < 100) continue;
if (ageX == ageY) {
// Same age: count[ageX] * (count[ageX] - 1)
result += count[ageX] * (count[ageX] - 1);
} else {
// Different ages: count[ageX] * count[ageY]
result += count[ageX] * count[ageY];
}
}
}
return result;
}
};
class Solution:
def numFriendRequests(self, ages: List[int]) -> int:
count = [0] * 121
for age in ages:
count[age] += 1
result = 0
for age_x in range(1, 121):
if count[age_x] == 0:
continue
for age_y in range(1, 121):
if count[age_y] == 0:
continue
# Check conditions
if age_y <= 0.5 * age_x + 7:
continue
if age_y > age_x:
continue
if age_y > 100 and age_x < 100:
continue
if age_x == age_y:
# Same age: count[age_x] * (count[age_x] - 1)
result += count[age_x] * (count[age_x] - 1)
else:
# Different ages: count[age_x] * count[age_y]
result += count[age_x] * count[age_y]
return result
public class Solution {
public int NumFriendRequests(int[] ages) {
int[] count = new int[121];
foreach (int age in ages) {
count[age]++;
}
int result = 0;
for (int ageX = 1; ageX <= 120; ageX++) {
if (count[ageX] == 0) continue;
for (int ageY = 1; ageY <= 120; ageY++) {
if (count[ageY] == 0) continue;
// Check conditions
if (ageY <= 0.5 * ageX + 7) continue;
if (ageY > ageX) continue;
if (ageY > 100 && ageX < 100) continue;
if (ageX == ageY) {
// Same age: count[ageX] * (count[ageX] - 1)
result += count[ageX] * (count[ageX] - 1);
} else {
// Different ages: count[ageX] * count[ageY]
result += count[ageX] * count[ageY];
}
}
}
return result;
}
}
var numFriendRequests = function(ages) {
const count = new Array(121).fill(0);
for (const age of ages) {
count[age]++;
}
let result = 0;
for (let ageX = 1; ageX <= 120; ageX++) {
if (count[ageX]
复杂度分析
| 复杂度类型 | 大小 |
|---|---|
| 时间复杂度 | O(A²)，其中 A = 120 是年龄的取值范围 |
| 空间复杂度 | O(A) = O(120) = O(1)，使用固定大小的计数数组 |