人们会互相发送好友请求，现在给定一个包含有他们年龄的数组，ages[i] 表示第 i 个人的年龄。
当满足以下条件时，A 不能给 B（A、B不为同一人）发送好友请求：
X: age[B] <= 0.5 * age[A] + 7
Y: age[B] > age[A]
Z: age[B] > 100 && age[A] < 100
否则，A 可以给 B 发送好友请求。
- 注意如果 A 向 B 发出了请求，不等于 B 接受了 A 的请求。而且，人们不会给自己发送好友请求。
求总共会发出多少份好友请求?
示例 :
输入: [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.
思路
- 由x可知发送者年龄必须>14岁
- 由Y可知,发送者必须更年长
- 由于Y的限制,Z的限制没有意义
- 可以先排序,然后使用规则计算发送份数,也可以利用集合或映射数组
代码1:
public int numFriendRequests(int[] ages) {
// 排序计数
Arrays.sort(ages);
int res = 0;
int temp = -1, count = 1;
for (int i = ages.length - 1; i >= 0; i--) {
int less = ages[i] / 2 + 7;
for (int j = 0; j <= i; j++) {
if (less < ages[j]) {
res += i - j;
break;
}
}
if (temp > 14 && ages[i] == temp) {
res += count;
count++;
} else {
count = 1;
temp = ages[i];
}
}
return res;
}
- 代码效率不高
- 排序后,进行发送份数计算,对于大于14岁且同龄者需要特别处理
- 在大于14岁下,年长者能够为所有年幼者发送申请
代码2:
public int numFriendRequests(int[] ages) {
// 映射数组
int nums[] = new int[121],sums[] = new int[121],res = 0;
//计算各个年龄段的人数
for( int i = 0;i < ages.length;i++) {
nums[ages[i]]++;
}
//计算年龄小于等于下标人数
for(int i = 1;i<121;i++) {
sums[i] = sums[i-1] + nums[i];
}
//低于15没朋友
for(int i = 15;i < 121;i++) {
if(nums[i] == 0) continue;
int count = sums[i] - sums[i/2+7];
//不包含自己
count--;
res += count * nums[i];
}
return res;
}
- 效率排行中,最快的代码
- 使用映射数组,存储各个年龄段的人数以及不大于该年龄段的人数
- 对于自身做特殊处理
- 低于15岁依然没有朋友
总结
- 只有一个特性的数组,非常适合映射(只需要你的大小值,不需要位置索引等)
- 注意排除题目中的干扰条件
- 同龄人互相发送以及自己不能发送自己是这道题的难点
