【面试高频题】难度 1.5/5，一道「桶排序 + 前缀和」优化题
【面试高频题】难度 1.5/5，一道「桶排序 + 前缀和」优化题
题目描述
这是 LeetCode 上的「825. 适龄的朋友」，难度为「中等」。
在社交媒体网站上有n 个用户。给你一个整数数组 ages ，其中
是第
个用户的年龄。
如果下述任意一个条件为真，那么用户 将不会向用户 y（x != y）发送好友请求：
否则，x 将会向y 发送一条好友请求。
注意，如果 x向 y发送一条好友请求， y不必也向 x发送一条好友请求。另外，用户不会向自己发送好友请求。
返回在该社交媒体网站上产生的好友请求总数。
示例 1：
输入：ages = [16,16]
输出：2
解释：2 人互发好友请求。
示例 2：
输入：ages = [16,17,18]
输出：2
解释：产生的好友请求为 17 -> 16 ，18 -> 17 。
示例 3：
输入：ages = [20,30,100,110,120]
输出：3
解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。
提示：
排序 + 双指针
从三个不发送好友请求的条件来看，以 y的角度来说，可总结为：年龄比我小的不考虑（同龄的可以），年龄比我大可以考虑，但是不能超过一定范围则不考虑。
即对于一个确定的 y而言，会发送好友请求的 x 范围为连续段：
随着 的逐渐增大，对应的 连续段的左右边界均逐渐增大（数轴上均往右移动）。
因此，我们可以先对ages 进行排序，枚举每个
，同时使用 i和 y维护左右区间，
代表在 ages上会往
发送请求的 x 连续段，统计每个
的 x 有多少个即是答案，同时需要注意在
范围内是包含
自身，统计区间长度时需要进行
操作。
代码：
class Solution {
public int numFriendRequests(int[] ages) {
Arrays.sort(ages);
int n = ages.length, ans = 0;
for (int k = 0, i = 0, j = 0; k < n; k++) {
while (i < k && !check(ages[i], ages[k])) i++;
if (j < k) j = k;
while (j < n && check(ages[j], ages[k])) j++;
if (j > i) ans += j - i - 1;
}
return ans;
}
boolean check(int x, int y) {
if (y <= 0.5 * x + 7) return false;
if (y > x) return false;
if (y > 100 && x < 100) return false;
return true;
}
}
- 时间复杂度：
- 空间复杂度：
桶排序 + 前缀和
在解法一中，复杂度的上界在于「双轴快排」，利用本题数据范围 1 <= ages[i] <= 120，值域较小，我们可以通过「桶排序」的方式进行排序优化。
假设对 ages进行桶排后得到的数组为nums ，其中
的含义为在 ages中年龄为 i 的人有cnt 个。
同时，我们发现在解法一中，我们枚举
，并使用 i和 j两个指针寻找连续的 x 段的过程， x会始终停留于值与
相等的最小下标处，而对于桶排数组而言，当前位置就是最小合法x 值（与 y 相等），因此我们只需要找到最大合法x 值的位置即可（对应解法一的 y位置）。
同样，最大 x 的位置在桶排数组中也是随着 y 的增大（右移）逐渐增大（右移）。
剩下的问题在于，如何统计桶排数组中连续段下标的和为多少（有多少个合法 x值），这可以直接在桶排数组应用前缀和即可。
代码：
class Solution {
int N = 130;
public int numFriendRequests(int[] ages) {
int[] nums = new int[N];
for (int i : ages) nums[i]++;
for (int i = 1; i < N; i++) nums[i] += nums[i - 1];
int ans = 0;
for (int y = 1, x = 1; y < N; y++) {
// 有 a 个 y
int a = nums[y] - nums[y - 1];
if (a == 0) continue;
if (x < y) x = y;
while (x < N && check(x, y)) x++;
// [y, x) 为合法的 x 范围，对于每个 y 而言，有 b 个 x
int b = nums[x - 1] - nums[y - 1] - 1;
if (b > 0) ans += b * a;
}
return ans;
}
boolean check(int x, int y) {
if (y <= 0.5 * x + 7) return false;
if (y > x) return false;
if (y > 100 && x < 100) return false;
return true;
}
}
- 时间复杂度：令 C为年龄值域大小，对于本题 C固定为130 。复杂度为
- 空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第 No.825 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。