跳转至

613. 直线上的最近距离 🔒

题目描述

表： Point

+-------------+------+
| Column Name | Type |
+-------------+------+
| x           | int  |
+-------------+------+
在SQL中，x是该表的主键列。
该表的每一行表示X轴上一个点的位置。

 

找到 Point 表中任意两点之间的最短距离。

返回结果格式如下例所示。

 

示例 1：

输入：
Point 表:
+----+
| x  |
+----+
| -1 |
| 0  |
| 2  |
+----+
输出：
+----------+
| shortest |
+----------+
| 1        |
+----------+
解释：点 -1 和 0 之间的最短距离为 |(-1) - 0| = 1。

 

进阶：如果 Point 表按 升序排列，如何优化你的解决方案？

解法

方法一：自连接

我们可以使用自连接，将表中的每个点与其他更大的点进行连接，然后计算两点之间的距离，最后取最小值。

1
2
3
4
5
# Write your MySQL query statement below
SELECT MIN(p2.x - p1.x) AS shortest
FROM
    Point AS p1
    JOIN Point AS p2 ON p1.x < p2.x;

方法二：窗口函数

我们也可以使用窗口函数，将表中的点按照 $x$ 排序，然后计算相邻两点之间的距离，最后取最小值。

1
2
3
4
5
# Write your MySQL query statement below
SELECT x - LAG(x) OVER (ORDER BY x) AS shortest
FROM Point
ORDER BY 1
LIMIT 1, 1;

评论