当前位置：网站首页>【有趣的编程题之适龄的朋友】（Leetcode原题详解）

【有趣的编程题之适龄的朋友】（Leetcode原题详解）

2022-04-22 09:35:00 【想挣钱】

朋友们，今天的题目是适龄的朋友

文章目录

一、题目要求
二、题目解析
三、逻辑分析
四、代码展示
五、总结

废话不多说，我们直接看题

一、题目要求

在这里插入图片描述

二、题目解析

对于发送好友请求的三个前提条件

通过简单的计算，我们可以发现，当条件三满足时，条件二一定满足。而发送好友请求的条件是三个条件都为假。
所以，我们只需要找到不满足条件一和条件二的ages[y]即可

即ages[y]需要满足下面式子：
在这里插入图片描述

三、逻辑分析

在这里插入图片描述

所以，我们可以先对ages数组进行升序排序，然后遍历ages[x]>=15的元素，ages[y]的区间就在
(0.5×ages[x]+7,ages[x]]之间

在这里插入图片描述

经过上面的分析，我们可以得出[left,right]就是所有ages[y]的区间，但是要注意ages[x]一定在这个区间中，故要将区间中元素个数-1，再将每一个ages[x]对应的元素个数累加，就是最终的结果

四、代码展示

static int cmp(const void * pa, const void * pb) {
    
    return *(int *)pa - *(int *)pb;
}

int numFriendRequests(int* ages, int agesSize){
    
    //用qsort函数对ages进行升序排序
    qsort(ages, agesSize, sizeof(int), cmp);
    int left = 0, right = 0, count = 0;
    for (int i = 0; i < agesSize; ++i) {
    
        //当ages[x]<15时，没有符合要求的ages[y]
        if (ages[i] < 15) {
    
            continue;
        }
        while (ages[left] <= 0.5 * ages[i] + 7) {
    
            ++left;
        }
        while (right + 1 < agesSize && ages[right + 1] <= ages[i]) {
    
            ++right;
        }
        count += right - left;
    }
    return count;
}