825. Friends Of Appropriate Ages

Problem

There are n persons on a social media website. You are given an integer array ages where ages[i] is the age of the i^th person.

A Person x will not send a friend request to a person y (x != y) if any of the following conditions is true:

age[y] <= 0.5 * age[x] + 7
age[y] > age[x]
age[y] > 100 && age[x] < 100

Otherwise, x will send a friend request to y.

Note that if x sends a request to y, y will not necessarily send a request to x. Also, a person will not send a friend request to himself.

Return the total number of friend requests made.

https://leetcode.cn/problems/friends-of-appropriate-ages/

Example 1:

Input: ages = [16,16]
Output: 2
Explanation: 2 people friend request each other.

Example 2:

Input: ages = [16,17,18]
Output: 2
Explanation: Friend requests are made 17 -> 16, 18 -> 17.

Example 3:

Input: ages = [20,30,100,110,120]
Output: 3
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

Constraints:

n == ages.length
1 <= n <= 2 * 10^4
1 <= ages[i] <= 120

Test Cases

1 2	class Solution: def numFriendRequests(self, ages: List[int]) -> int:

solution_test.py

import pytest

from solution import Solution

@pytest.mark.parametrize('ages, expected', [
    ([16,16], 2),
    ([16,17,18], 2),
    ([20,30,100,110,120], 3),
])
class Test:
    def test_solution(self, ages, expected):
        sol = Solution()
        assert sol.numFriendRequests(ages) == expected

Thoughts

第三个条件似乎没用？当 age[y] > 100 && age[x] < 100 成立的时候，第二条的 age[y] > age[x] 一定成立。

条件一对应图中斜线下方的梯形区域，条件二对应对角线上方的三角形区域，条件三是条件二区域内部靠上部分的那个长条矩形。

排除掉三个条件的限制，图中网格填充的三角形区域是会发送邀请的 age[y] 和 age[x] 的关系，即 0.5 * age[x] + 7 < age[y] <= age[x]。

因为年龄数值是 1 到 120 之间的整数，用桶排序，统计每个年龄的人数，并算出小于等于每个年龄的总人数。

对于任何一个年龄，计算这个年龄的人会给哪个年龄范围的人发邀请，算出这个年龄区间的总人数。

空间复杂度 O(1)，时间复杂度 O(n)。

Code

solution.py

from typing import List


class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        counts = [0] * 121
        for age in ages:
            counts[age] += 1

        for age in range(1, len(counts)):
            counts[age] += counts[age - 1]

        total = 0
        for age_x in range(1, len(counts)):
            count_x = counts[age_x] - counts[age_x - 1]
            if count_x == 0:
                continue

            exclude_age_y = (age_x >> 1) + 7
            if age_x < exclude_age_y + 1:
                continue

            count_y = counts[age_x] - counts[exclude_age_y] - 1 # Exclude himself.
            total += count_x * count_y

        return total

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。