LeetCode 825. Friends Of Appropr

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

当满足以下条件时，A 不能给 B（A、B不为同一人）发送好友请求：

X: age[B] <= 0.5 * age[A] + 7
Y: age[B] > age[A]
Z: age[B] > 100 && age[A] < 100
否则，A 可以给 B 发送好友请求。

• 注意如果 A 向 B 发出了请求，不等于 B 接受了 A 的请求。而且，人们不会给自己发送好友请求。

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

示例 :

输入: [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.
说明:

• 1 <= ages.length <= 20000.
• 1 <= ages[i] <= 120.

思路

• 由x可知发送者年龄必须>14岁
• 由Y可知,发送者必须更年长
• 由于Y的限制,Z的限制没有意义
• 可以先排序,然后使用规则计算发送份数,也可以利用集合或映射数组

代码1:

    public int numFriendRequests(int[] ages) {
        // 排序计数
        Arrays.sort(ages);
        int res = 0;
        int temp = -1, count = 1;
        for (int i = ages.length - 1; i >= 0; i--) {
            int less = ages[i] / 2 + 7;
            for (int j = 0; j <= i; j++) {
                if (less < ages[j]) {
                    res += i - j;
                    break;
                }
            }
            if (temp > 14 && ages[i] == temp) {
                res += count;
                count++;
            } else {
                count = 1;
                temp = ages[i];
            }
        }

        return res;
    }

• 代码效率不高
• 排序后,进行发送份数计算,对于大于14岁且同龄者需要特别处理
• 在大于14岁下,年长者能够为所有年幼者发送申请

代码2:

    public int numFriendRequests(int[] ages) {
        // 映射数组
        int nums[] = new int[121],sums[] = new int[121],res = 0;
        //计算各个年龄段的人数
        for( int i = 0;i < ages.length;i++) {
            nums[ages[i]]++;
        }
        //计算年龄小于等于下标人数
        for(int i = 1;i<121;i++) {
            sums[i] = sums[i-1] + nums[i];
        }
        //低于15没朋友
        for(int i = 15;i < 121;i++) {
            if(nums[i] == 0) continue; 
            int count = sums[i] - sums[i/2+7];
            //不包含自己
            count--;
            res += count * nums[i];
        }
        return res;
    }

• 效率排行中,最快的代码
• 使用映射数组,存储各个年龄段的人数以及不大于该年龄段的人数
• 对于自身做特殊处理
• 低于15岁依然没有朋友

总结

1. 只有一个特性的数组,非常适合映射(只需要你的大小值,不需要位置索引等)
2. 注意排除题目中的干扰条件
3. 同龄人互相发送以及自己不能发送自己是这道题的难点