Leetcode 825:适龄的朋友(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 825:适龄的朋友(超详细的解法!!!)

in leetcode with 0 comment

人们会互相发送好友请求,现在给定一个包含有他们年龄的数组,ages[i]表示第i个人的年龄。

当满足以下条件时,A 不能给 B(A、B不为同一人)发送好友请求:

否则,A 可以给 B 发送好友请求。

注意如果 A 向 B 发出了请求,不等于 B 也一定会向 A 发出请求。而且,人们不会给自己发送好友请求。

求总共会发出多少份好友请求?

示例 1:

输入: [16,16]
输出: 2
解释: 二人可以互发好友申请。

示例 2:

输入: [16,17,18]
输出: 2
解释: 好友请求可产生于 17 -> 16, 18 -> 17.

示例 3:

输入: [20,30,100,110,120]
输出: 3
解释: 好友请求可产生于 110 -> 100, 120 -> 110, 120 -> 100.

说明:

解题思路

首先分析一下这个问题,第二个条件和第三个条件实际上是一样的,并且第二个条件覆盖了第三个条件。对于数组中的数,我们只需要找到不满足第一个条件和第二个条件的数有几个即可。

如果我们将数组按照从小到大的顺序排序,我们可以通过lower_bound找到两个下界的位置。关于lower_bound看这里Leetcode 二分法问题总结(超详细!!!)

根据age[A] > age[B] >= 0.5 * age[A] + 7我们可以推出age[A]>14,所以这里有一个剪枝的操作。

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        res, n = 0, len(ages)
        ages.sort()
        for a in ages:
            if a <= 14: # 剪枝
                continue
            r, l = bisect.bisect(ages, a), bisect.bisect(ages, a//2 + 7)
            if l > r:
                res +=  r - l - 1 #-1减去自己
        return res

这个解法的时间复杂度是O(nlogn),非常不错!但是有更快的。

我们可以统计[1, 120]个年龄的每个年龄对应的人数,然后计算前缀和(关于前缀和可以阅读Leetcode 1124:表现良好的最长时间段(超详细的解法...),这样我们就可以在O(1)的时间内算出(0.5 * age[A] + 7, age[A]]这个年龄区间内的所有人数。

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        cnt, pre = [0] * 121, [0] * 121
        for a in ages:
            cnt[a] += 1

        for i in range(1, 121):
            pre[i] = pre[i-1] + cnt[i]
        
        res = 0
        for i in range(15, 121):
            res += (pre[i] - pre[i//2 + 7] - 1) * cnt[i]
        return res

但是有一个小问题,如果将age[A] > age[B] >= 0.5 * age[A] + 7变成(age[B] - 7)*2 >= age[A] > age[B],那么第一种解法就要写成

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        res, n = 0, len(ages)
        ages.sort()
        for b in ages:
            if b <= 14: # 剪枝
                continue
            r, l = bisect.bisect_left(ages, (b - 7)*2), bisect.bisect_left(ages, b)
            if r > l:
                res +=  r - l - 1 #-1减去自己
        return res

而第二种写法就要写成

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        cnt, pre = [0] * 248, [0] * 248
        for a in ages:
            cnt[a] += 1

        for i in range(1, 248):
            pre[i] = pre[i-1] + cnt[i]
        
        res = 0
        for i in range(15, 121):
            res += (pre[2*(i - 7) - 1] - pre[i- 1] - 1) * cnt[i]
        return res

reference:

https://leetcode.com/problems/friends-of-appropriate-ages/discuss/127341/10ms-concise-Java-solution-O(n)-time-and-O(1)-space

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses