Some people will make friend requests. The list of their ages is given and ages[i]
is the age of the ith person.
Person A will NOT friend request person B (B != A) if any of the following conditions are true:
age[B] <= 0.5 * age[A] + 7
age[B] > age[A]
age[B] > 100 && age[A] < 100
Otherwise, A will friend request B.
Note that if A requests B, B does not necessarily request A. Also, people will not friend request themselves.
How many total friend requests are made?
Example 1:
Input: [16,16] Output: 2 Explanation: 2 people friend request each other.
Example 2:
Input: [16,17,18] Output: 2 Explanation: Friend requests are made 17 -> 16, 18 -> 17.
Example 3:
Input: [20,30,100,110,120] Output: Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.
Notes:
-
1 <= ages.length <= 20000
. -
1 <= ages[i] <= 120
.
考虑到数据规模,先用hashmap存ages中的年龄和出现次数。checkRequest(a, b)检查年龄a是否会对年龄b发起friend request。遍历ages,如果年龄a会对年龄b发起request,如果a != b,这一对pair产生的request总数= map[a] * map[b];如果a = b,这一对pair产生的request总数要去除自己对自己的friend request,即map[a] * (map[a] - 1)
注意:check的顺序,应该先check是否会request再计算数量,年龄相同的两个人不一定会相互request
time: O(N^2), space: O(N)
class Solution { public int numFriendRequests(int[] ages) { Map<Integer, Integer> map = new HashMap<>(); for(int i : ages) { map.put(i, map.getOrDefault(i, 0) + 1); } int cnt = 0; for(Integer i : map.keySet()) { for(Integer j : map.keySet()) { if(checkRequest(i, j)) { if(i != j) cnt += map.get(i) * map.get(j); else cnt += map.get(i) * (map.get(i) - 1); } } } return cnt; } private boolean checkRequest(int A, int B) { if(B <= 0.5 * A + 7) return false; if(B > A) return false; if(B > 100 && A < 100) return false; return true; } }
reference: https://leetcode.com/problems/friends-of-appropriate-ages/discuss/127029/C++JavaPython-Easy-and-Straight-Forward