适龄的朋友

标签: 数组双指针二分查找排序

难度: Medium

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

Submission

运行时间: 40 ms

内存: 16.8 MB

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        # age[y] <= 0.5 * age[x] + 7                age[y] > 0.5 * age[x] + 7
        # age[y] > age[x]                           age[y] <= age[x] # the last age[y] <= age[x]
        # age[y] > 100 && age[x] < 100
        # ages.sort()
        # res = 0
        # n = len(ages)

        # def binary_search_larger_than(val, left, right):
        #     if not (-1 < left < n and -1 < right < n):
        #         return -1
        #     l, r = left, right
        #     while l + 1 < r:
        #         m = l + (r - l) // 2
        #         if ages[m] < val:
        #             l = m
        #         elif ages[m] == val:
        #             l = m
        #         else:
        #             r = m
        #     if ages[l] > val:
        #         return l
        #     if ages[r] > val:
        #         return r
        #     return -1
        
        # def binary_search_less_equal(val, left, right):
        #     if not (-1 < left < n and -1 < right < n):
        #         return -1
        #     l, r = left, right
        #     while l + 1 < r:
        #         m = l + (r - l) // 2
        #         if ages[m] < val:
        #             l = m
        #         elif ages[m] == val:
        #             l = m
        #         else:
        #             r = m
        #     if ages[r] <= val:
        #         return r
        #     if ages[l] <= val:
        #         return l
        #     return -1

        # for i, age in enumerate(ages):
        #     val = int(0.5 * age) + 7
        #     lower = binary_search_larger_than(val, 0, i)
        #     upper = binary_search_less_equal(age, i, n - 1)
        #     if lower != -1 and upper != -1:
        #         res += upper - lower # not include themself
        
        # return res

        res = 0
        ages_count = [0] * 121
        for age in ages:
            ages_count[age] += 1

        pref_sum = [0] * 121
        for i in range(1, 121):
            pref_sum[i] = pref_sum[i - 1] + ages_count[i]
        
        # for i in ages:
        for i in range(1, 121):
            if ages_count[i] == 0: continue
            val = int(0.5 * i) + 7
            # for age in range(val + 1, i + 1):
            #     if ages_count[age] > 0:
            #         res += ages_count[age]
            #     if age == i:
            #         res -= 1
            if i > val:
                res += (pref_sum[i] - pref_sum[val] - 1) * ages_count[i] 
        return res

Explain

This solution utilizes a frequency array to count the occurrences of each age from 1 to 120. It creates a prefix sum array to quickly calculate the sum of frequencies up to any given age. The logic involves iterating over each age and determining the range of ages that can receive friend requests from that age based on the given conditions. For each valid age, the solution calculates the number of potential friend requests by multiplying the frequency of the current age by the number of users in the valid age range (using the prefix sum to find this number quickly). This method avoids the need for nested iterations over the `ages` array, thus improving efficiency.

时间复杂度: O(n)

空间复杂度: O(1)

# Class definition for the solution
class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        # Initialize result and frequency array for ages
        res = 0
        ages_count = [0] * 121

        # Count frequency of each age
        for age in ages:
            ages_count[age] += 1

        # Create prefix sum array for cumulative age counts
        pref_sum = [0] * 121
        for i in range(1, 121):
            pref_sum[i] = pref_sum[i - 1] + ages_count[i]

        # Calculate friend requests for each age
        for i in range(1, 121):
            if ages_count[i] == 0: continue
            val = int(0.5 * i) + 7
            if i > val:
                res += (pref_sum[i] - pref_sum[val] - 1) * ages_count[i] 
        return res

Explore

在这个条件下，我们需要计算能发送好友请求的最小年龄`y`。根据条件`ages[y] <= 0.5 * ages[x] + 7`，我们将`y`设为`0.5 * i + 7`的最大整数值。为了确保`y`是有效的，我们使用向下取整的方式（因为年龄为整数），即`y = floor(0.5 * i + 7)`。例如，如果`i`为20，那么`0.5 * 20 + 7 = 17`，有效的最小`y`就是18（因为17是不包括在内的），所以我们从18岁开始计算能接受的好友请求。

这里的`pref_sum`数组是年龄的累积频数，即`pref_sum[i]`表示从1岁到`i`岁的用户总数。`val`是根据`0.5 * i + 7`规则计算得到的最小年龄。`pref_sum[i] - pref_sum[val]`计算的是年龄在`(val, i]`范围内的用户数。由于年龄为`i`的用户不能向自己发送好友请求，所以需要再减去1，即`-1`部分。这样，`pref_sum[i] - pref_sum[val] - 1`就准确地表示了年龄为`i`的用户可以发送的好友请求数量。

`pref_sum`数组是一个累积和数组，其中`pref_sum[i]`表示从1岁到`i`岁所有年龄的用户总数。每个`pref_sum[i]`可以通过`pref_sum[i-1]`（即前一个年龄的累积和）加上当前年龄`i`的用户数`ages_count[i]`计算得到。这样，每次计算只需要当前和前一个元素的值，因此不需要额外的循环。这是因为前缀和的性质使得每个元素的计算仅依赖于其前一个元素，从而实现了高效的累计计算。

在没有前缀和数组的情况下，我们可能需要对每个年龄`i`，遍历所有可能的年龄`y`来检查是否满足好友请求的条件，这就需要嵌套迭代。通过使用前缀和数组，我们可以直接通过`pref_sum`快速计算在任意年龄范围内的用户数，从而避免了对每个年龄进行二次迭代的需要。例如，对于每个年龄`i`，通过一次查找就可以得到范围内的用户总数，大大减少了总体的计算次数，提高了算法的效率。