盛日辉的博客
0%

Leetcode_1583. 统计不开心的朋友

发表于 更新于 分类于

题目

1583. 统计不开心的朋友
难度：中等

给你一份 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 与 u 的亲近程度胜过 x 与 y，且
  • u 与 x 的亲近程度胜过 u 与 v

因此我们的做法就是：

  1. 找到一个x，以及和他配对的y;
  2. 在x的preferences里遍历，在没有遇到y之前，每一个都是可能的u;（这时满足了第一个条件）
  3. 在找到与这个u配对的v，然后在u的preferences里找x和v的下标关系是否满足第二个条件，即如果在u的preferences里x的下标小于v的下标，那么，x就是不开心的。
    为了找所有不开心的x，那么，就是要遍历所有人，同时还要方便找到与它配对的y，所以再开始的时候先创建一个字典，用于记录每个人和谁配对。
    具体代码实现的时候，还有一个x_isunhappy用于标记x是不是不开心的，如果是，就可以去下一个x了。

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def unhappyFriends(n, preferences, pairs):
        if n == 2:
            return 0
        unhappy = 0
        pairs_dict = {}
        for x, y in pairs:
            pairs_dict[x] = y
            pairs_dict[y] = x
        for x in range(n):
            y = pairs_dict[x]
            x_isunhappy = False
            for u in preferences[x]:
                if u == y or x_isunhappy == True:
                    break
                v = pairs_dict[u]
                if preferences[u].index(x) < preferences[u].index(v):
                    x_isunhappy = True
                    unhappy += 1

        return unhappy
    官方的方法和我的几乎一样。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    class Solution:
        def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
            order = [[0] * n for _ in range(n)]
            for i in range(n):
                for j in range(n - 1):
                    order[i][preferences[i][j]] = j
            
            match = [0] * n
            for x, y in pairs:
                match[x] = y
                match[y] = x

            unhappyCount = 0
            for x in range(n):
                y = match[x]
                index = order[x][y]
                for i in range(index):
                    u = preferences[x][i]
                    v = match[u]
                    if order[u][x] < order[u][v]:
                        unhappyCount += 1
                        break
            
            return unhappyCount

    # 作者：LeetCode-Solution
    # 链接：https://leetcode-cn.com/problems/count-unhappy-friends/solution/tong-ji-bu-kai-xin-de-peng-you-by-leetcode-solutio/
    # 来源：力扣（LeetCode）
    # 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

提交记录

提交记录.jpg