825. 适龄的朋友

题目描述

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。

如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：

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

否则，x 将会向 y 发送一条好友请求。

注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。

返回在该社交媒体网站上产生的好友请求总数。

示例 1：

输入：ages = [16,16]
输出：2
解释：2 人互发好友请求。

示例 2：

输入：ages = [16,17,18]
输出：2
解释：产生的好友请求为 17 -> 16 ，18 -> 17 。

示例 3：

输入：ages = [20,30,100,110,120]
输出：3
解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。

提示：

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

解法

方法一：计数 + 枚举

我们可以用一个长度为 \(121\) 的数组 \(\textit{cnt}\) 记录每个年龄的人数。

接下来，枚举所有可能的年龄对 \((\textit{ax}, \textit{ay})\)，如果 \(\textit{ax}\) 和 \(\textit{ay}\) 不满足题目中的任意一个条件，这些年龄对 \((\textit{ax}, \textit{ay})\) 就可以互发好友请求。

此时，如果 \(\textit{ax} = \textit{ay}\)，年龄相同，那么 \(\textit{ax}\) 和 \(\textit{ay}\) 之间的好友请求数为 \(\textit{cnt}[\textit{ax}] \times (\textit{cnt}[\textit{ax}] - 1)\)；否则，年龄不同，那么 \(\textit{ax}\) 和 \(\textit{ay}\) 之间的好友请求数为 \(\textit{cnt}[\textit{ax}] \times \textit{cnt}[\textit{ay}]\)。我们将这些好友请求数累加到答案中即可。

时间复杂度 \(O(n + m^2)\)，其中 \(n\) 是数组 \(\textit{ages}\) 的长度，而 \(m\) 是年龄的最大值，本题中 \(m = 121\)。

Python3JavaC++GoTypeScript

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        cnt = [0] * 121
        for x in ages:
            cnt[x] += 1
        ans = 0
        for ax, x in enumerate(cnt):
            for ay, y in enumerate(cnt):
                if not (ay <= 0.5 * ax + 7 or ay > ax or (ay > 100 and ax < 100)):
                    ans += x * (y - int(ax == ay))
        return ans

class Solution {
    public int numFriendRequests(int[] ages) {
        final int m = 121;
        int[] cnt = new int[m];
        for (int x : ages) {
            ++cnt[x];
        }
        int ans = 0;
        for (int ax = 1; ax < m; ++ax) {
            for (int ay = 1; ay < m; ++ay) {
                if (!(ay <= 0.5 * ax + 7 || ay > ax || (ay > 100 && ax < 100))) {
                    ans += cnt[ax] * (cnt[ay] - (ax == ay ? 1 : 0));
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        const int m = 121;
        vector<int> cnt(m);
        for (int x : ages) {
            ++cnt[x];
        }
        int ans = 0;
        for (int ax = 1; ax < m; ++ax) {
            for (int ay = 1; ay < m; ++ay) {
                if (!(ay <= 0.5 * ax + 7 || ay > ax || (ay > 100 && ax < 100))) {
                    ans += cnt[ax] * (cnt[ay] - (ax == ay ? 1 : 0));
                }
            }
        }
        return ans;
    }
};

func numFriendRequests(ages []int) (ans int) {
    cnt := [121]int{}
    for _, x := range ages {
        cnt[x]++
    }
    for ax, x := range cnt {
        for ay, y := range cnt {
            if ay <= ax/2+7 || ay > ax || (ay > 100 && ax < 100) {
                continue
            }
            if ax == ay {
                ans += x * (x - 1)
            } else {
                ans += x * y
            }
        }
    }

    return
}

function numFriendRequests(ages: number[]): number {
    const m = 121;
    const cnt = Array(m).fill(0);
    for (const x of ages) {
        cnt[x]++;
    }

    let ans = 0;
    for (let ax = 0; ax < m; ax++) {
        for (let ay = 0; ay < m; ay++) {
            if (ay <= 0.5 * ax + 7 || ay > ax || (ay > 100 && ax < 100)) {
                continue;
            }
            ans += cnt[ax] * (cnt[ay] - (ax === ay ? 1 : 0));
        }
    }

    return ans;
}

825. 适龄的朋友

题目描述

解法

方法一：计数 + 枚举

评论