Leetcode_825_Friends_Of_Appropriate_Ages

发表于 |

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:

1.age[B] <= 0.5 * age[A] + 7
2.age[B] > age[A]
3.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: 3
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

Notes:
1 <= ages.length <= 20000.
1 <= ages[i] <= 120.

分析：
对于A这个人交朋友来说，根据条件2比他年级大的一概排除，比他年级小的要满足条件1，条件3没用，不知道这个出题的人在想什么，注意数据长度达到20000，所以复杂度n^2是不行的

思路：
首先将ages数组从大到小排序，然后用两个指针遍历即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def numFriendRequests(ages):
    if len(ages) == 1: return 0
    ages.sort(reverse=True)
    i,j = 0,1
    res = 0
    cnt = 0
    while i < len(ages):
        while j < len(ages) and ages[j] > 0.5*ages[i] + 7:
            j += 1
        # 如果对于age[0]来说,age[1,2,3,4,5]他都可以交朋友
        # 那么对于age[1]来说,age[2,3,4,5]也是必可以的，所以只用遍历一遍就可以了
        res += j - i - 1
        i += 1
        if i < len(ages) and ages[i] > 14:
            if ages[i] == ages[i-1]: res += cnt + 1;cnt += 1
            else: cnt = 0
        if i >= j: j = i + 1
    return res

"difficulty: medium
83 / 83 test cases passed
runtime: 305 ms"