发表于 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 题目链接