825. 适龄的朋友
在社交媒体网站上有 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 发送一条好友请求。另外,用户不会向自己发送好友请求。
返回在该社交媒体网站上产生的好友请求总数。
早上被这种阅读理解题整的我有点爆炸
主要关键是我不能理解第一个用例
输入:
ages = [16,16]
输出:
2
解释:
2 人互发好友请求。
那你为什么还在题目中特别强调了这是互发是不必要的呢
所以这就是所谓的不必要吗?
把我整麻了
姑且还是放一下我的错误做法吧
public class Solution { public int NumFriendRequests(int[] ages) { Array.Sort(ages); int left = 0; int right = ages.Length-1; int ans = 0; while(left <= right) { if(left == right) { left++; right = ages.Length-1; continue; } if(ages[left] > 100 && ages[right] < 100) { right--; } else if(ages[left] <= (ages[right]*0.5 + 7)) { right--; } else { ans++; if(ages[left] == ages[right]) { ans++; } right--; } } return ans; } }
我的思路也是二分 但是我是用计数的方式的
所以遇到像这种极端用例又超时了
唉
贴贴官方题解的思路吧
思路差距在于
提炼条件可得0.5×ages[x]+7<ages[y]≤ages[x]
只需要 考虑年龄大于15的情况
x 发送的好友请求数,即为 [left,right] 区间的长度减去 1
将每一个 x 对应的[left,right] 区间长度减去 1 进行累加
就可以得到最终的答案
public class Solution { public int NumFriendRequests(int[] ages) { int n = ages.Length; Array.Sort(ages); int left = 0, right = 0, ans = 0; foreach (int age in ages) { if (age < 15) { continue; } while (ages[left] <= 0.5 * age + 7) { ++left; } while (right + 1 < n && ages[right + 1] <= age) { ++right; } ans += right - left; } return ans; } } 作者:LeetCode-Solution 链接:https://leetcode-cn.com/problems/friends-of-appropriate-ages/solution/gua-ling-de-peng-you-by-leetcode-solutio-v7yk/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。