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
.
按年龄大小排序,O(n) time, O(1) space. 因为年龄是有限的1-120
题目中第3个条件是多余的
class Solution { public int numFriendRequests(int[] ages) { int[] ageMap = new int[121]; for (int age : ages) { ageMap[age]++; } int rt = 0; for (int i = 120; i > 0; i--) { if (ageMap[i] == 0) continue; int cutOff = (int)(0.5 * i + 7) + 1; if (cutOff > i) continue; int cutOffNum = 0; for (int j = cutOff; j < i; j++) { cutOffNum += ageMap[j]; } rt += cutOffNum * ageMap[i] + (ageMap[i] - 1) * ageMap[i]; } return rt; } }
No comments:
Post a Comment