Medium

题目描述

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

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

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

但是，这样的配对情况可能会是其中部分朋友感到不开心。在 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
  • xi != yi
  • 0 <= xi, yi <= n - 1
  • 每位朋友都恰好被包含在一对中

解题思路

这道题考查的是图论和模拟的思想。关键在于理解"不开心"的定义：朋友 x 不开心需要同时满足两个条件。

解题思路：

  1. 预处理偏好关系：将偏好列表转换为排名矩阵 rank，其中 rank[i][j] 表示朋友 i 对朋友 j 的偏好排名（排名越小表示越喜欢）。这样可以在 O(1) 时间内比较偏好关系。

  2. 建立配对映射：创建一个映射表 partner，记录每个人的配对对象。

  3. 遍历检查：对每个人 x，检查是否存在另一个人 u 使得：

    • x 对 u 的偏好胜过对当前配对 y 的偏好
    • u 对 x 的偏好胜过对当前配对 v 的偏好

  4. 优化策略：由于偏好列表是按优先级排序的，我们只需要检查比当前配对更受偏好的朋友即可。

时间复杂度为 O(n²)，空间复杂度为 O(n²)。这是一个典型的模拟题，核心是正确理解题意并高效实现判断逻辑。

代码实现

class Solution {
public:
    int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
        // 构建排名矩阵，rank[i][j] 表示朋友 i 对朋友 j 的偏好排名
        vector<vector<int>> rank(n, vector<int>(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < preferences[i].size(); j++) {
                rank[i][preferences[i][j]] = j;
            }
        }
        
        // 构建配对映射
        vector<int> partner(n);
        for (auto& pair : pairs) {
            partner[pair[0]] = pair[1];
            partner[pair[1]] = pair[0];
        }
        
        int unhappy = 0;
        for (int x = 0; x < n; x++) {
            int y = partner[x];
            int yRank = rank[x][y];
            
            // 检查所有比当前配对更受偏好的朋友
            for (int i = 0; i < yRank; i++) {
                int u = preferences[x][i];
                int v = partner[u];
                
                // 检查 u 是否也更偏好 x 而不是当前配对 v
                if (rank[u][x] < rank[u][v]) {
                    unhappy++;
                    break;
                }
            }
        }
        
        return unhappy;
    }
};

class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
        # 构建排名矩阵
        rank = [[0] * n for _ in range(n)]
        for i in range(n):
            for j, friend in enumerate(preferences[i]):
                rank[i][friend] = j
        
        # 构建配对映射
        partner = [0] * n
        for x, y in pairs:
            partner[x] = y
            partner[y] = x
        
        unhappy = 0
        for x in range(n):
            y = partner[x]
            y_rank = rank[x][y]
            
            # 检查所有比当前配对更受偏好的朋友
            for i in range(y_rank):
                u = preferences[x][i]
                v = partner[u]
                
                # 检查 u 是否也更偏好 x 而不是当前配对 v
                if rank[u][x] < rank[u][v]:
                    unhappy += 1
                    break
        
        return unhappy

public class Solution {
    public int UnhappyFriends(int n, int[][] preferences, int[][] pairs) {
        // 构建排名矩阵
        int[,] rank = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < preferences[i].Length; j++) {
                rank[i, preferences[i][j]] = j;
            }
        }
        
        // 构建配对映射
        int[] partner = new int[n];
        foreach (var pair in pairs) {
            partner[pair[0]] = pair[1];
            partner[pair[1]] = pair[0];
        }
        
        int unhappy = 0;
        for (int x = 0; x < n; x++) {
            int y = partner[x];
            int yRank = rank[x, y];
            
            // 检查所有比当前配对更受偏好的朋友
            for (int i = 0; i < yRank; i++) {
                int u = preferences[x][i];
                int v = partner[u];
                
                // 检查 u 是否也更偏好 x 而不是当前配对 v
                if (rank[u, x] < rank[u, v]) {
                    unhappy++;
                    break;
                }
            }
        }
        
        return unhappy;
    }
}

var unhappyFriends = function(n, preferences, pairs) {
    // 构建排名矩阵
    const rank = Array(n).fill().map(() => Array(n).fill(0));
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < preferences[i].length; j++) {
            rank[i][preferences[i][j]] = j;
        }
    }
    
    // 构建配对映射
    const partner = Array(n);
    for (const [x, y] of pairs) {
        partner[x] = y;
        partner[y] = x;
    }
    
    let unhappy = 0;
    for (let x = 0; x < n; x++) {
        const y = partner[x];
        const yRank = rank[x][y];
        
        // 检查所有比当前配对更受偏好的朋友
        for (let i = 0; i < yRank; i++) {
            const u = preferences[x][i];
            const v = partner[u];
            
            // 检查 u 是否也更偏好 x 而不是当前配对 v
            if (rank[u][x] < rank[u][v]) {
                unhappy++;
                break;
            }
        }
    }
    
    return unhappy;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²)
空间复杂度O(n²)