当前位置：网站首页>leetcode825. Age appropriate friends

leetcode825. Age appropriate friends

2022-07-04 06:48:00 【2021dragon】

Insert picture description here

LeetCode Series articles

List of articles

One 、 Title Description
Two 、 Example
3、 ... and 、 Main idea
Four 、 Code implementation

One 、 Title Description

On social media sites $n$ Users . Give you an array of integers $a g e s$ , among $ages[i](1\leq ages[i] \leq 120)$ It's No $i$ Age of users .

If any of the following conditions is true , So users $x$ The user will not be $y$ Send friend request ：
$ages[y]\leq0.5\times ages[x]+7$
$a g e s [y] > a g e s [x]$
$ages[y]>100\&\&ages[x]<100$
otherwise , $x$ Will $y$ Send a friend request .

Be careful , If $x$ towards $y$ Send a friend request , $y$ You don't have to $x$ Send a friend request . in addition , Users will not send friend requests to themselves .

Returns the total number of friend requests generated on this social media site .

Two 、 Example

Input ： ages = [16, 16]
Output ： 2

explain ： 2 People send friend requests to each other .

3、 ... and 、 Main idea

1、 Violence solution

It is very simple to solve the problem with violent solution , To determine which users a user can send friend requests , Just traverse this $n - 1$ （ Not including myself ） Users , Judge whether the conditions for sending friend requests are met in turn .

Obviously, the time complexity of this violent solution is $O(N^2)$ , When the amount of user data is too large, the computing time will soar , Therefore, this solution is not recommended .

2、 Sort + Double pointer

Carefully observe the three conditions given by the topic , You will find that condition three is actually contained in condition two , If condition 3 is met, condition 2 must be met , So as long as the first two conditions are not met , So users $x$ You can tell users $y$ Send friend request , That is, users $y$ Need to meet ： $0.5\times ages[x]+7<ages[y]\leq ages[x]$

This relationship is represented by a number axis as follows ：
Insert picture description here
If there are users who meet the requirements $y$ , that $0.5\times x+7<x$ , namely $x > 14$ . in other words , If a user's age is less than or equal to 14, Then the user will not be able to send friend requests to any user .

Now it seems , Want to know the user $x$ To which users $y$ Send friend request , In fact, it is necessary to find the corresponding left and right boundaries on the number axis , Users whose age is in this area are users $x$ Users who can send friend requests .

When looking for the left and right boundaries, you can use $l e f t$ and $r i g h t$ Subscript indicating the left and right boundaries （ Double pointer ）, If you use closed intervals on both sides , namely $l e f t$ It points to the first user who meets the requirements , $r i g h t$ It refers to the last user who meets the requirements , So in the end $r i g h t - l e f t$ The value of is the user who meets the requirements $y$ The number of .（ Be careful ： It's not here $r i g h t - l e f t + 1$ , Because the user $x$ It is also in the region , But users $x$ Don't send friend requests to yourself ）
Insert picture description here
So the steps to solve the problem are as follows ：

To the given $n$ Sort by the age of users .
Traverse this one by one $n$ Age of users .
When traversing users , If the user's age is less than or equal to 14, Then the number of friend requests that the user can send out is 0; If the user is older than 14, Then find the area that meets the transmission requirements through the double pointer , Then we can get the number of friend requests that the user can send out .
Finally, add up the number of friend requests that each user can send out .

Particular attention , When determining the age area that meets the requirements through the double pointer , Only for the first time $n$ Search from scratch based on users . Later, when determining the area , The left and right boundaries of the region only need to be searched backwards based on the left and right boundaries of the previous user . because $0.5\times x+7$ And $x$ It's a linear relationship , When $x$ When it increases , $0.5\times x+7$ The value of will also increase , So we don't need to judge the last user's $l e f t$ Whether the user's age before the pointer is in this limited area .

3、 Count sorting + The prefix and

If you look closely, you will find that the age of the given user of the title is $[1, 120]$ Within the scope of , Therefore, we can count and sort the number of users of all ages .

For example, we store the sorting results in $c n t$ In the array , here $c n t [a g e]$ It means that the age is $a g e$ Number of users , And each age is $a g e$ The number of friend requests that users can send out is ： $(\sum_{i=0.5\times age+8}^{age}cnt[i])-1$ , One minus one is because users will not send friend requests to themselves .

To avoid traversing every time $c n t$ Sum arrays , We can calculate $c n t$ Array prefix and array $p r e$ , $p r e [a g e]$ It represents the age group located in 1 ~ age Number of users ： $pre[age]=\sum_{i=1}^{age}cnt[i]$ .

At this time, each age is $a g e$ The number of friend requests that users can send out can be written as ： $pre[age]-pre[0.5\times age+7]-1$
Insert picture description here
At this point, we can $O (1)$ Calculate an age of $a g e$ The number of friend requests that users of can send out , Multiply this value by $c n t [a g e]$ It is the total number of friend requests that all users in this age group can send out .

So the steps to solve the problem are as follows ：

Count and sort the number of users in each age group .
Count out $c n t$ Array prefix and array $p r e$ .
adopt $(pre[age]-pre[0.5\times age+7]-1)\times cnt[age]$ The formula calculates the total number of friend requests that users of each age group can send out , Adding them up is the final result .