【一日双题—见微知著】一道简单+中等题——适龄朋友+合并有序数组（都可以用双指针，略有不同）

• • 一、中等题 825. 适龄的朋友
  • • 1.1题目描述
    • 1.2题目分析
    • 1.3代码实现
  • 二、简单题 88. 合并两个有序数组
  • • 2.1思路
    • 2.2 代码实现
  • 结尾

在社交媒体网站上有 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 发送一条好友请求。另外，用户不会向自己发送好友请求。

返回在该社交媒体网站上产生的好友请求总数。

由于条件2 如果y.age>x.age那么x不会向y发送好友请求，即只会向比自己年龄小Or同龄发送好友请求（条件3意思为小于100岁的人不会给大于100岁的人发好友请求，包含在条件2内）

条件1说明如果y.age 得出x的好友请求发送范围如下
【x.age *0.5+7，x.age】

在一个排序数组上，可用两个指针分别指向边界，相减可得请求数，随着x的增大同样递增边界即可，排序需要时间为（nlogn），下面介绍一种更巧妙的方法：

先一次历遍统计每个年龄人数的多少，用 Cnt[i] 表示，年龄范围为0~120；然后用另外一个数组统计小于等于年龄i的人数，即 Pre[i] 表示 age<=i 的人数

现在我们判断某一年纪 K 的人应该发送的好友请求如下：

Pre[ K ] - Pre[ (int)(0.5*K+7-1) ] - 1

已统计 K 年龄有Cnt[K]人，即

Cnt[K] * ( Pre[ K ] - Pre[ (int)(0.5*K+7-1) ] - 1 )

将每个年龄段的人的结果相加即可的答案

class Solution {
    public int numFriendRequests(int[] ages) {
        int[] cnt = new int[121];
        //统计人数
        for (int age : ages) {
            cnt[age]++;
        }

        //累加统计小于等于某年龄人数
        int[] pre = new int[121];
        for (int i = 1; i <= 120; ++i) {
            pre[i] = pre[i - 1] + cnt[i];
        }

        //若x.age<15,有y<=15不发送，而y>x不发送，矛盾
        int ans = 0;
        for (int i = 15; i <= 120; ++i) {
            if (cnt[i] > 0) {
                int bound = (int) (i * 0.5 + 8);//+8保证进位
                ans += cnt[i] * (pre[i] - pre[bound - 1] - 1);
            }
        }
        return ans;
    }
}

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

很简单的双指针，不过要注意额外开一个数组复制nums1，避免将nums2填充到nums1时覆盖原值，这里介绍一种投机取巧的办法，将nums2复制到nums1的空缺处，然后调用 Array.sort() 排序算法，结果还挺快的，如下

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2,0,nums1,m,nums2.length);
        Arrays.sort(nums1);
    }
}

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems

关注作者，带你刷题，从简单的算法题了解最常用的算法技能（算法题解双日一更）
每日同类型两道算法题——简单到进阶，让你不知不觉成为无情的刷题机器