leetcode
leetcode 1401 ~ 1450
统计不开心的朋友

统计不开心的朋友

难度:

标签:

题目描述

代码结果

运行时间: 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列表中?
在这个问题的上下文中,所有的朋友都被配对了,而且每个朋友的preferences列表包含了所有其他的朋友(除了他们自己)。由于每个人都有一个配对,并且配对的人也在他们的preferences列表中,因此在遍历x的preferences时,每个u的配对v总是存在于u的preferences列表中。这是由题目的设定保证的,即每个人都与除自己外的所有人有明确的亲近程度顺序。
🦆
在函数check中,为什么在遇到u == y时就可以直接break,而不是继续检查其他可能的u是否会使x不开心?
在函数`check`中,当遇到`u == y`时可以直接break的原因是,preferences列表是按亲近程度从高到低排列的。一旦遇到了x的配对y,意味着后面的所有u都不会比y更亲近于x。既然x最亲近的朋友到y为止都没有使x不开心,那么排在y后面的朋友就更不会了。因此,可以在遇到y时停止进一步检查。
🦆
算法中使用了双重遍历preferences的方式,这种方法是否最优或存在更高效的方法来减少重复的操作?
算法使用了双重遍历preferences来确定不开心的朋友,这种方法确实可以解决问题,但不是最优的。一种可能的优化方法是,首先对每个人的preferences列表建立一个快速查找表(如哈希表),以记录每个朋友在该列表中的索引位置。这样,在检查是否不开心时,可以直接通过索引比较来判断亲近程度而不是遍历列表。这样可以将时间复杂度从O(n^2)降低到更有效率的级别。
🦆
在构建配对关系时,为什么选择使用defaultdict(int)而不是普通的字典,是考虑到了哪些特殊情况?
在构建配对关系时,使用`defaultdict(int)`而非普通字典主要是为了代码的便利性和默认值处理。使用`defaultdict(int)`可以自动为尚未显式设置的键提供一个整数类型的默认值0,这在某些情况下可以避免额外的键存在检查。然而,在这个特定的算法实现中,使用普通字典也是完全可行的,因为每个配对关系都会被明确设置。因此,这里使用`defaultdict(int)`主要是出于编程习惯或者简化代码的考虑,而不是必须的需求。

相关问题