How can binary search be used in Friends Of Appropriate Ages?

Binary search helps by efficiently finding the range of ages that can send a friend request to a given person. This reduces the number of comparisons needed, speeding up the solution.

Why is sorting necessary in Friends Of Appropriate Ages?

Sorting helps arrange the ages in increasing order, making it easier to apply binary search and use two pointers to efficiently count valid pairs.

What are common mistakes in solving Friends Of Appropriate Ages?

Common mistakes include neglecting to handle edge cases, making incorrect age comparisons, and failing to optimize the solution with sorting and binary search.

How does GhostInterview optimize the solving process?

GhostInterview helps by providing focused guidance on sorting, binary search, and two-pointer techniques, allowing you to quickly implement an efficient solution.

Can the problem be solved without sorting the array?

While it is possible to solve the problem without sorting, using sorting and binary search is the most efficient approach for this problem, reducing time complexity.

#825

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

适龄的朋友

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。如果下述任意一个条件为真，那么用户 x 将不会向用户 y （ x != y ）发送好友请求： ages[y] ages[y] > ages[x] ages[y] > 100 && ages[…

数组双指针二分查找排序

题目描述

在社交媒体网站上有 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

lightbulb

解题思路

方法一：计数 + 枚举

我们可以用一个长度为 $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$ 。

1

2

3

4

5

6

7

8

9

10

11

12

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of binary search and two-pointer techniques.
question_mark
Candidate suggests sorting as a first step for optimization.
question_mark
Candidate efficiently calculates the number of valid requests without resorting to brute force.

warning

常见陷阱

外企场景

error
Forgetting to handle edge cases, such as when people have very young or very old ages.
error
Incorrectly calculating the valid age range for friend requests, especially when ages are close to boundaries.
error
Attempting to brute force the solution without leveraging sorting and binary search for optimization.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implement a solution without sorting the array, using only binary search to determine valid pairs.
arrow_right_alt
Modify the problem to allow for weighted age differences when determining valid requests.
arrow_right_alt
Adapt the problem for real-time computations with streaming data, requiring constant updates to the array of ages.

help

常见问题

外企场景

继续练习

#826 安排工作以达到最大收益 #786 第 K 个最小的质数分数 #719 找出第 K 小的数对距离