跳转至

2978. 对称坐标 🔒

题目描述

表： Coordinates

+-------------+------+
| Column Name | Type |
+-------------+------+
| X           | int  |
| Y           | int  |
+-------------+------+
每一行包括 X 和 Y，都是整数。表格可能包含重复值。

如果两个坐标 (X1, Y1) 和 (X2, Y2) 满足条件 X1 == Y2 和 X2 == Y1，则它们被称为 对称 坐标。

编写一个解决方案，找出在所有这些对称坐标中，满足条件 X1 <= Y1 的唯一坐标。

按照 X 和 Y 分别 升序 排列结果表。

结果格式如下示例所示。

 

示例 1:

输入：
Coordinates table:
+----+----+
| X  | Y  |
+----+----+
| 20 | 20 |
| 20 | 20 |
| 20 | 21 |
| 23 | 22 |
| 22 | 23 |
| 21 | 20 |
+----+----+
输出：
+----+----+
| x  | y  |
+----+----+
| 20 | 20 |
| 20 | 21 |
| 22 | 23 |
+----+----+
解释：
- (20, 20) 和 (20, 20) 是对称坐标，因为 X1 == Y2 和 X2 == Y1。所以 (20, 20) 被显示为独特的坐标。
- (20, 21) 和 (21, 20) 是对称坐标，因为 X1 == Y2 和 X2 == Y1。然而，只有 (20, 21) 会被显示，因为 X1 <= Y1。
- (23, 22) 和 (22, 23) 是对称坐标，因为 X1 == Y2 和 X2 == Y1。然而，只有 (22, 23) 会被显示，因为 X1 <= Y1。
输出表按照 X 和 Y 升序排列。

解法

方法一：窗口函数 + 自连接

思考

对称点对满足 \((x,y)\) 与 \((y,x)\) 都出现且不是同一行。表中可能有重复坐标，需用行号区分。\(ROW_NUMBER\) 生成 \(id\) 后自连接：\(p1.x=p2.y\) 且 \(p1.y=p2.x\)，并限制 \(p1.x \le p1.y\)、\(id\) 不同，以免重复输出与自配对。

最后对坐标去重排序。

我们可以使用窗口函数 ROW_NUMBER() 来为每一行添加一个自增的序号，然后再自连接两张表，连接条件为 p1.x = p2.y AND p1.y = p2.x AND p1.x <= p1.y AND p1.id != p2.id，最后再排序去重即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
# Write your MySQL query statement below
WITH
    P AS (
        SELECT
            ROW_NUMBER() OVER () AS id,
            x,
            y
        FROM Coordinates
    )
SELECT DISTINCT
    p1.x,
    p1.y
FROM
    P AS p1
    JOIN P AS p2 ON p1.x = p2.y AND p1.y = p2.x AND p1.x <= p1.y AND p1.id != p2.id
ORDER BY 1, 2;

评论