825.适龄的朋友

链接：825.适龄的朋友
难度：Medium
标签：数组、双指针、二分查找、排序
简介：在社交媒体网站上有 n 个用户。返回在该社交媒体网站上产生的好友请求总数。

题解 1 - cpp

• 编辑时间：2021-12-27
• 执行用时：1320ms
• 内存消耗：36.5MB
• 编程语言：cpp
• 解法介绍：排序后双指针移动。

class Solution {
   public:
    int numFriendRequests(vector<int>& ages) {
        sort(ages.begin(), ages.end());
        int n = ages.size(), ans = 0;
        for (int l = 0, r = 0; r < n; r++) {
            while (l < r && ages[l] <= ages[r] / 2.0 + 7) l++;
            ans += r - l;
            if (ages[r] / 2.0 + 7 < ages[r]) {
                int tmp = r;
                while (tmp + 1 < n && ages[tmp + 1] == ages[tmp]) {
                    ans++;
                    tmp++;
                }
            }
        }
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2021-12-27
• 执行用时：108ms
• 内存消耗：36.2MB
• 编程语言：cpp
• 解法介绍：二分查找最小值和最大值。

class Solution {
   public:
    int bs(vector<int>& ages, double num) {
        int l = 0, r = ages.size(), m;
        while (l < r) {
            m = (l + r) / 2;
            if (ages[m] > num)
                r = m;
            else
                l = m + 1;
        }
        return l;
    }
    int numFriendRequests(vector<int>& ages) {
        sort(ages.begin(), ages.end());
        int n = ages.size(), ans = 0;
        for (int i = 0; i < n; i++) {
            double min = ages[i] / 2.0 + 7, max = ages[i];
            if (min > max) continue;
            int imin = bs(ages, min), imax = bs(ages, max);
            if (imin < imax) ans += imax - imin - 1;
        }
        return ans;
    }
};

题解 3 - cpp

• 编辑时间：2021-12-27
• 执行用时：56ms
• 内存消耗：36.3MB
• 编程语言：cpp
• 解法介绍：双指针移动。

class Solution {
   public:
    int numFriendRequests(vector<int>& ages) {
        sort(ages.begin(), ages.end());
        int n = ages.size(), l = 0, r = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            if (ages[i] * 0.5 + 7 > ages[i]) continue;
            while (r + 1 < n && ages[r + 1] <=ages[i]) r++;
            while (l < r && ages[l] <= ages[i] * 0.5 + 7) l++;
            ans += r - l;
        }
        return ans;
    }
};

题解 4 - undefined

• 编辑时间：2024-11-17
• 执行用时：205ms
• 内存消耗：17.11MB
• 编程语言：undefined
• 解法介绍：对于每个用户进行二分查找合适的区间。

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        ages.sort()
        res = 0
        for x in range(len(ages)):
            starty = bisect_right(ages, 0.5 * ages[x] + 7)
            endy = bisect_right(ages, ages[x])
            if ages[x] < 100: endy = min(endy, bisect_right(ages, 100))
            if starty < endy: res += endy - starty
            if starty <= x < endy: res -= 1
        return res