---

1583. 统计不开心的朋友

• 标签：数组、模拟
• 难度：中等

题目链接

• 1583. 统计不开心的朋友 - 力扣

题目大意

描述：给定 $n$ 位朋友（$n$ 为偶数），编号 $0 \sim n-1$。以及一个 $n \times n$ 的二维数组 $preferences$，其中 $preferences[i]$ 是一个长度为 $n-1$ 的排列，按亲近程度从高到低排列了 $i$ 的所有其他朋友。

另外给定一个 $n/2 \times 2$ 的二维数组 $pairs$，表示已经配对的 $n/2$ 对朋友。

如果一对朋友 $(x, y)$ 配对，但存在另一对朋友 $(u, v)$ 配对，使得：

• $x$ 与 $u$ 的亲近程度高于 $x$ 与 $y$（即 $u$ 在 $x$ 的 preferences 中排在 $y$ 前面）。
• $u$ 与 $x$ 的亲近程度高于 $u$ 与 $v$（即 $x$ 在 $u$ 的 preferences 中排在 $v$ 前面）。

则称 $x$ 是不开心的。

要求：返回不开心的朋友数量。

说明：

• $2 \le n \le 500$。
• $n$ 为偶数。
• $preferences[i]$ 长度为 $n-1$，是 $0 \sim n-1$ 除 $i$ 外所有数的排列。
• $pairs$ 长度为 $n/2$，且每个朋友恰好出现一次。

示例：

• 示例 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 都开心。

解题思路

思路 1：模拟 + 哈希表

1. 核心思想

不开心的定义：对于配对 $(x, y)$，如果存在另一配对 $(u, v)$，使得 $x$ 更亲近 $u$（胜过 $y$）且 $u$ 更亲近 $x$（胜过 $v$），则 $x$ 不开心。

简单模拟：建立一个亲近程度排名矩阵 $rank[i][j]$，表示 $j$ 在 $i$ 的 preferences 中的位置（越小越亲近）。

对于每个配对 $(x, y)$，检查所有其他配对 $(u, v)$ 是否满足条件。

2. 具体步骤

第 1 步：建立 $rank$ 矩阵。$rank[i][j] = k$ 表示 $j$ 是 $i$ 的第 $k$ 亲近的朋友（$k$ 越小越亲近）。

第 2 步：建立配对映射 $pair\_map$，$pair\_map[x] = y$ 表示 $x$ 的配对对象。

第 3 步：对每个配对 $(x, y)$：

• 遍历 $x$ 的 preferences 中排在 $y$ 之前的所有人 $u$（即比 $y$ 更亲近的人）。
• 找到 $u$ 的配对对象 $v = pair\_map[u]$。
• 检查 $rank[u][x] < rank[u][v]$（$u$ 更亲近 $x$ 胜过其配对对象）。
• 如果成立，$x$ 不开心，计数加一并跳出。

第 4 步：返回不开心总数。

3. 正确性证明

• 条件中 $x$ 和 $u$ 相互更亲近（$x$ 更亲近 $u$ 胜过 $y$，且 $u$ 更亲近 $x$ 胜过 $v$），这种"单向更喜欢"的关系会使 $x$ 不开心。
• 注意条件是不对称的：$x$ 不开心只需要存在一个满足条件的 $u$，而不是 $u$ 也必须不开心。
• 遍历所有配对，检查每个人的所有可能 $u$，时间复杂度 $O(n^2)$。

4. 举例说明

以 $n=4, preferences=[[1,2,3],[3,2,0],[3,1,0],[1,2,0]], pairs=[[0,1],[2,3]]$ 为例：

配对：

• $(0, 1)$
• $(2, 3)$

检查 $x=0$（配 $y=1$）：

• $0$ 的 preferences: $[1,2,3]$，排在 $1$ 前面的人：无（$1$ 排第一）。
• 没有更亲近的 $u$，不满足条件。

检查 $x=1$（配 $y=0$）：

• $1$ 的 $preferences: [3,2,0]$，排在 $0$ 前面的人：$3, 2$。
  • $u=3$，$v = pair\_map[3] = 2$。$rank[3][1] = 0$（因为 $3$ 的 preference 是 $[1,2,0]$，$1$ 排第 0），$rank[3][2] = 1$。$0 < 1$，满足条件！$1$ 不开心。
  • $u=2$，$v = pair\_map[2] = 3$。$rank[2][1] = 1$（$2$ 的 preference $[3,1,0]$），$rank[2][3] = 0$。$1 < 0$ 不满足。

所以 $1$ 不开心，总数为 $1$。

思路 1：代码

class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
        # rank[i][j] = k 表示 j 在 i 的 preferences 中的位置（0-based）
        rank = [[0] * n for _ in range(n)]
        for i in range(n):
            for k, j in enumerate(preferences[i]):
                rank[i][j] = k

        # 配对映射
        pair_map = {}
        for x, y in pairs:
            pair_map[x] = y
            pair_map[y] = x

        unhappy = set()

        for x, y in pairs:
            # 检查 x
            for u in preferences[x]:
                if u == y:
                    break
                v = pair_map[u]
                if rank[u][x] < rank[u][v]:
                    unhappy.add(x)
                    break

            # 检查 y
            for u in preferences[y]:
                if u == x:
                    break
                v = pair_map[u]
                if rank[u][y] < rank[u][v]:
                    unhappy.add(y)
                    break

        return len(unhappy)

思路 1：复杂度分析

• 时间复杂度：$O(n^2)$，对每个人最多遍历其 preferences（长度 $n-1$）。
• 空间复杂度：$O(n^2)$，rank 矩阵。