统计不开心的朋友
难度:
标签:
题目描述
代码结果
运行时间: 42 ms, 内存: 27.8 MB
/*
* 思路:
* 1. 为了快速找到某个朋友的配对,可以用一个数组 pairMap 来存储每个朋友的配对。
* 2. 为了快速找到某个朋友在其他朋友中的亲近程度排名,可以用一个二维数组 rank 来存储。
* 3. 使用 Java Stream API 进行数据处理和遍历。
*/
import java.util.*;
import java.util.stream.*;
public class UnhappyFriendsStream {
public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
int[] pairMap = new int[n];
int[][] rank = new int[n][n];
Arrays.stream(pairs).forEach(pair -> {
pairMap[pair[0]] = pair[1];
pairMap[pair[1]] = pair[0];
});
IntStream.range(0, n).forEach(i -> {
IntStream.range(0, preferences[i].length).forEach(j -> {
rank[i][preferences[i][j]] = j;
});
});
return (int) IntStream.range(0, n).filter(x -> {
int y = pairMap[x];
return IntStream.range(0, rank[x][y]).anyMatch(i -> {
int u = preferences[x][i];
int v = pairMap[u];
return rank[u][x] < rank[u][v];
});
}).count();
}
}
解释
方法:
这道题目的核心是检查每对朋友中的一个是否不开心。对于每对配对的朋友x和y,我们需要检查有没有其他的朋友u,满足u和x的亲近程度超过y,且u的配对朋友v与x的亲近程度低于u。为了方便查找每个朋友的配对,我们首先使用一个哈希表g来存储每个朋友的配对情况。然后对每对配对的朋友x和y,我们分别检查x和y是否不开心。如果x不开心,我们检查他在preferences中排序前于y的每一个朋友u,检查u对应的配对v,看v是否在u的preferences中排在x前面。如果满足这些条件,x就不开心。重复同样的过程对y进行检查。最后,累加所有不开心的朋友数量即可得到结果。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
如何确保在遍历x的preferences时,对于每个u,其配对v总是存在于u的preferences列表中?
▷🦆
在函数check中,为什么在遇到u == y时就可以直接break,而不是继续检查其他可能的u是否会使x不开心?
▷🦆
算法中使用了双重遍历preferences的方式,这种方法是否最优或存在更高效的方法来减少重复的操作?
▷🦆
在构建配对关系时,为什么选择使用defaultdict(int)而不是普通的字典,是考虑到了哪些特殊情况?
▷