JZX轻语：简

LeetCode 825 - 适龄的朋友

发表于2024年05月12日

#排序 #二分法 #数组

通过整理条件可知，x加上y的条件满足0.5 * ages[x] + 7 < ages[y] <= ages[x]。因此，先对用户按年龄排序，然后从小到大遍历用户，使用二分法找到可添加的用户群即可。需要注意的是同年龄用户的处理，对于n个同龄用户，我们可以跳过前n - 1个同龄用户的处理，处理第n个用户后，将其结果乘以n即可。

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        ages.sort()
        ans = 0
        same_cnt = 1  # 连续重复年龄的个数

        for i in range(0, len(ages)):
            age = ages[i]
            if i + 1 < len(ages) and age == ages[i + 1]:
                # 如果后面还有重复的，+1并跳过
                same_cnt += 1
                continue
            # 后面不是重复的了, 通过二分法找到第一个满足> 0.5 * ages[x] + 7的用户位置lo
            # 然后可添加的好友位置为 lo..i-1

            lo = 0
            hi = i - 1
            bar = 0.5 * age + 7

            while lo <= hi:
                mid = (lo + hi) >> 1
                if ages[mid] > bar:
                    hi = mid - 1
                else:
                    lo = mid + 1

            # 需要乘上重复年龄的个数
            ans += (i - lo) * same_cnt
            same_cnt = 1

        return ans

闪念标签：LC

题目链接：https://leetcode.cn/problems/friends-of-appropriate-ages/description/