统计不开心的朋友

难度: Medium

给你一份 n 位朋友的亲近程度列表，其中 n 总是偶数。

对每位朋友 i，preferences[i] 包含一份 按亲近程度从高到低排列 的朋友列表。换句话说，排在列表前面的朋友与 i 的亲近程度比排在列表后面的朋友更高。每个列表中的朋友均以 0 到 n-1 之间的整数表示。

所有的朋友被分成几对，配对情况以列表 pairs 给出，其中 pairs[i] = [x_i, y_i] 表示 x_i 与 y_i 配对，且 y_i 与 x_i 配对。

但是，这样的配对情况可能会使其中部分朋友感到不开心。在 x 与 y 配对且 u 与 v 配对的情况下，如果同时满足下述两个条件，x 就会不开心：

x 与 u 的亲近程度胜过 x 与 y，且
u 与 x 的亲近程度胜过 u 与 v

返回 不开心的朋友的数目 。

示例 1：

输入：n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]]
输出：2
解释：
朋友 1 不开心，因为：
- 1 与 0 配对，但 1 与 3 的亲近程度比 1 与 0 高，且
- 3 与 1 的亲近程度比 3 与 2 高。
朋友 3 不开心，因为：
- 3 与 2 配对，但 3 与 1 的亲近程度比 3 与 2 高，且
- 1 与 3 的亲近程度比 1 与 0 高。
朋友 0 和 2 都是开心的。

示例 2：

输入：n = 2, preferences = [[1], [0]], pairs = [[1, 0]]
输出：0
解释：朋友 0 和 1 都开心。

示例 3：

输入：n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]], pairs = [[1, 3], [0, 2]]
输出：4

提示：

2 <= n <= 500
n 是偶数
preferences.length == n
preferences[i].length == n - 1
0 <= preferences[i][j] <= n - 1
preferences[i] 不包含 i
preferences[i] 中的所有值都是独一无二的
pairs.length == n/2
pairs[i].length == 2
x_i != y_i
0 <= x_i, y_i <= n - 1
每位朋友都恰好被包含在一对中

Submission

运行时间: 42 ms

内存: 27.8 MB

class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
        p = preferences
        g = defaultdict(int)
        for u, v in pairs:
            g[u] = v
            g[v] = u
        ans = 0
        def check(x, y):
            for u in p[x]:
                if u == y:
                    break
                v = g[u]
                for w in p[u]:
                    if w == v:
                        break
                    if w == x:
                        return 1
            return 0

        for x, y in pairs:
            ans += check(x, y) + check(y, x)
        return ans

Explain

这道题目的核心是检查每对朋友中的一个是否不开心。对于每对配对的朋友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)

class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
        p = preferences
        g = defaultdict(int)
        for u, v in pairs:  # 构建配对关系
            g[u] = v
            g[v] = u
        ans = 0
        def check(x, y):  # 检查x是否不开心
            for u in p[x]:  # 遍历x的preferences
                if u == y:
                    break
                v = g[u]  # 获取u的配对朋友v
                for w in p[u]:  # 遍历u的preferences
                    if w == v:
                        break
                    if w == x:
                        return 1  # 如果找到x排在v前面，x不开心
            return 0
        for x, y in pairs:  # 检查每一对配对
            ans += check(x, y) + check(y, x)
        return ans

Explore

在这个问题的上下文中，所有的朋友都被配对了，而且每个朋友的preferences列表包含了所有其他的朋友（除了他们自己）。由于每个人都有一个配对，并且配对的人也在他们的preferences列表中，因此在遍历x的preferences时，每个u的配对v总是存在于u的preferences列表中。这是由题目的设定保证的，即每个人都与除自己外的所有人有明确的亲近程度顺序。

在函数`check`中，当遇到`u == y`时可以直接break的原因是，preferences列表是按亲近程度从高到低排列的。一旦遇到了x的配对y，意味着后面的所有u都不会比y更亲近于x。既然x最亲近的朋友到y为止都没有使x不开心，那么排在y后面的朋友就更不会了。因此，可以在遇到y时停止进一步检查。

算法使用了双重遍历preferences来确定不开心的朋友，这种方法确实可以解决问题，但不是最优的。一种可能的优化方法是，首先对每个人的preferences列表建立一个快速查找表（如哈希表），以记录每个朋友在该列表中的索引位置。这样，在检查是否不开心时，可以直接通过索引比较来判断亲近程度而不是遍历列表。这样可以将时间复杂度从O(n^2)降低到更有效率的级别。

在构建配对关系时，使用`defaultdict(int)`而非普通字典主要是为了代码的便利性和默认值处理。使用`defaultdict(int)`可以自动为尚未显式设置的键提供一个整数类型的默认值0，这在某些情况下可以避免额外的键存在检查。然而，在这个特定的算法实现中，使用普通字典也是完全可行的，因为每个配对关系都会被明确设置。因此，这里使用`defaultdict(int)`主要是出于编程习惯或者简化代码的考虑，而不是必须的需求。