0825._Friends_Of_Appropriate_Ages.md

825. Friends Of Appropriate Ages

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/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:

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.

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******

一看到这种刚好卡时间点的题目就应该想到要set一下，去除没有必要的重复计算， beats 52.58%

class Solution(object):
    def numFriendRequests(self, ages):
        """
        :type ages: List[int]
        :rtype: int
        """
        cnt = collections.Counter(ages)
        ages = sorted(set(ages), reverse=True)
        res = 0
        for i in range(len(ages)):
            A = ages[i]
            for j in range(i+1, len(ages)):
                B = ages[j]
                if A == B:
                    continue
                if B > 0.5 * A + 7:
                    res += cnt[A] * cnt[B] # 几个A * 几个B
        for age, person in cnt.items():
            if person > 1:
                if age > 0.5 * age + 7:
                    res += person * (person - 1)                
        return res