leetcode刷题日记-825. 适龄的朋友

leetcode刷题日记-825. 适龄的朋友

• 题目描述：
  在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。
  如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：
  age[y] <= 0.5 * age[x] + 7
  age[y] > age[x]
  age[y] > 100 && age[x] < 100
  否则，x 将会向 y 发送一条好友请求。
  注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。
  返回在该社交媒体网站上产生的好友请求总数。

• 示例：
  输入：ages = [16,16]
  输出：2
  解释：2 人互发好友请求。
  输入：ages = [16,17,18]
  输出：2
  解释：产生的好友请求为 17 -> 16 ，18 -> 17 。
  输入：ages = [20,30,100,110,120]
  输出：3
  解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。

• 提示：
  n == ages.length
  1 <= n <= 2 * 104
  1 <= ages[i] <= 120

• 解析：这个题目虽然不难，但是比较具有代表性。我们仔细观察一下发送好友请求的条件，如果x要给y发送好友请求，首先x要大于等于y，其次0.5 /* x + 7要小于y，我们发现当x=14的时候0.5 /* x + 7=14，也就是当x<=14时，所有的小于x的y均不满足0.5 /* x + 7 100 && age[x] < 100这个条件其实是无效的。很容易想到我们通过x要大于等于y这个条件，找到小于等于x的y，通过0.5 /* x + 7

• 针对排序后的数组，我们再考虑有效的两个条件，首先0.5 /* x + 7=y，即x可以向与他相等的y发送好友请求，也就是在x的右边找到满足x=y的最右边的y，到这里，这题的考点就呼之欲出了-双指针。针对右边的双指针，我们可以取巧，因为，我们只需要知道x对应的元素个数k，就知道右指针的位置了-（k-1），对于左指针，我们需要保留前一次遍历的位置，例如我们对数组从小到大进行遍历，对于k位置的x，他的左指针的位置一定会小于等于k+1位置的x，这样我们就避免了重复初始化左指针和重复遍历。因为有公式0.5 /* x + 7x2时，0.5 /* x1 + 7>0.5 /* x2 + 7，其对应的y1>y2。

• 解题代码如下：

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        """
        给定一个年龄数组，返回在该社交媒体网站上产生的好友请求总数
        >>>self.numFriendRequests([20,30,100,110,120])
        >>>3
        """
        n = len(ages)
        ages.sort()
        countV = Counter(ages)
        left, ans= 0, 0
        prev = 0    #记录前一个age对应的好友请求数
        for i in range(n):
            if ages[i] < 15:
                continue
            #相同的age有相同的好友请求数，避免left指针过多计算
            if i > 0 and ages[i] == ages[i-1]:
                ans += prev
                continue
            while ages[left] <= 0.5 * ages[i] + 7:
                left += 1
            prev = (i - left + countV[ages[i]] - 1)
            ans += prev
        return ans

• 代码解析：上述代码用一个计数器代替了right指针。总时间复杂度为 O(n log n)，也就是排序需要的时间，但是总的来说时间计算应该是n log n + n(计数器生成) + n（遍历数组和维护left指针）。用计数器理论上并不会变得更快，但是花里胡哨一点。
• 如果大家觉得有帮助，欢迎点个免费的赞，谢谢！