Skip to content

Latest commit

 

History

History
140 lines (111 loc) · 3.95 KB

README.md

File metadata and controls

140 lines (111 loc) · 3.95 KB
Raw
comments difficulty edit_url tags
true
中等
数据库

3058. 没有共同朋友的朋友 🔒

English Version

题目描述

表：Friends

+-------------+------+
| Column Name | Type |
+-------------+------+
| user_id1    | int  |
| user_id2    | int  |
+-------------+------+
(user_id1, user_id2) 是这张表的主键（有不同值的列组合）。
每一行包含 user id1, user id2，两人都是朋友。

编写一个解决方案来找到彼此是朋友但 没有共同 朋友的 所有用户对。

以 user_id1, user_id2 升序 返回结果表。

结果格式如下所示。

 

示例 1：

输入：
Friends 表：
+----------+----------+
| user_id1 | user_id2 | 
+----------+----------+
| 1        | 2        | 
| 2        | 3        | 
| 2        | 4        | 
| 1        | 5        | 
| 6        | 7        | 
| 3        | 4        | 
| 2        | 5        | 
| 8        | 9        | 
+----------+----------+
输出：
+----------+----------+
| user_id1 | user_id2 | 
+----------+----------+
| 6        | 7        | 
| 8        | 9        | 
+----------+----------+
解释： 
- 用户 1 和 2 是彼此的好友，但他们有一个用户 ID 为 5 的共同好友，因此结果不包含这一对。
- 用户 2 和 3 是朋友，他们有一个用户 ID 为 4 的共同好友，因此排除，类似地，对于具有用户 ID 为 3 的共同朋友的用户 2 和 4，也因此不包括在内。
- 用户 1 和 5 是彼此的好友，但他们有一个用户 ID 为 2 的共同好友，所以结果不包含这一对。
- 用户 6 和 7，与用户 8 和 9 一样，是彼此的好友，同时他们没有共同的好友，因此包含在结果中。
- 用户 3 和 4 是彼此的朋友，但他们有用户 ID 为 2 的共同好友，与用户 2 和 5 有用户 ID 为 1 的共同好友一样，因此被排除。
输出表以 user_id1 升序排列。

解法

方法一：子查询

我们先把所有的朋友关系都列出来，记录在 T 表中。然后再找出 没有共同朋友的朋友 🔒 对。

接下来，我们可以使用子查询来找出没有共同朋友的朋友 🔒 对，即这个朋友对不属于其他某个人的朋友。

MySQL

# Write your MySQL query statement below
WITH
    T AS (
        SELECT user_id1, user_id2 FROM Friends
        UNION ALL
        SELECT user_id2, user_id1 FROM Friends
    )
SELECT user_id1, user_id2
FROM Friends
WHERE
    (user_id1, user_id2) NOT IN (
        SELECT t1.user_id1, t2.user_id1
        FROM
            T AS t1
            JOIN T AS t2 ON t1.user_id2 = t2.user_id2
    )
ORDER BY 1, 2;

Python3

import pandas as pd


def friends_with_no_mutual_friends(friends: pd.DataFrame) -> pd.DataFrame:
    cp = friends.copy()
    t = cp[["user_id1", "user_id2"]].copy()
    t = pd.concat(
        [
            t,
            cp[["user_id2", "user_id1"]].rename(
                columns={"user_id2": "user_id1", "user_id1": "user_id2"}
            ),
        ]
    )
    merged = t.merge(t, left_on="user_id2", right_on="user_id2")
    ans = cp[
        ~cp.apply(
            lambda x: (x["user_id1"], x["user_id2"])
            in zip(merged["user_id1_x"], merged["user_id1_y"]),
            axis=1,
        )
    ]
    return ans.sort_values(by=["user_id1", "user_id2"])