1583. Count Unhappy Friends¶
题目信息¶
- 题号:
1583
- 难度:
Medium
- 主题:
数组、偏好排名、配对
- 原题:
- 重点:
对已配对的
x-y,若存在u-v使 x 更偏好 u 且 u 也更偏好 x,则 x 不开心
题目重述¶
有偶数个朋友,preferences[x] 按偏好从高到低列出除 x 外的所有人。pairs 把每个人恰好配对一次。
若 x 与 y 配对,但存在另一对中的 u,使 x 更喜欢 u 而不是 y,同时 u 更喜欢 x 而不是自己的搭档,则 x 不开心。请返回不开心朋友的数量。
2 <= n <= 500,n 为偶数,所有偏好列表都是合法排列。
自建示例¶
同一朋友可以因另一对中的成员而不开心:
输入:n = 4, preferences = [[1,2,3],[0,2,3],[0,1,3],[0,1,2]], pairs = [[0,3],[1,2]]
输出:3
解释:0 与 1 互相更偏好;2 与 0 也互相优先于各自搭档,因此 0、1、2 不开心。
每个人都与首选对象配对时无人不开心:
输入:n = 4, preferences = [[1,2,3],[0,2,3],[3,0,1],[2,0,1]], pairs = [[0,1],[2,3]]
输出:0
解释:每个人的搭档都是其偏好列表第一位。