1583. Count Unhappy Friends

题目信息

题号:

1583

难度:

Medium

主题:

数组、偏好排名、配对

原题:

LeetCode 1583

重点:

对已配对的 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
解释:每个人的搭档都是其偏好列表第一位。