LeetCode 612. 平面上的最近距离
题目描述
题意分析
表中的
(x, y)表示平面上的点，要求任意两个不同点之间的最短欧氏距离，并把结果四舍五入到两位小数，输出列名为shortest。需要比较的是点对，不能让一个点和自己配对，否则零距离会成为错误答案。当前官方题目的表名为
Point2D，下面按这个名字查询。
解法：SQL 自连接枚举点对
核心思路
[!blue]
为同一张点表指定p1、p2两个别名，自连接就可以枚举两个点的组合。为了排除自身，并避免把同一对点正反算两次，只保留坐标按字典序递增的方向：p1.x < p2.x，或者横坐标相同且p1.y < p2.y。对任意两个不同坐标，若横坐标不同，只有横坐标较小的点放在前面时成立；若横坐标相同，则由纵坐标决定唯一方向。因此每对不同点都被保留一次，竖直方向的点对也不会遗漏。
每对点的距离为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$，对应 SQL 中的
SQRT与POW。用MIN从所有点对中取最短距离，再由外层ROUND(..., 2)统一四舍五入。没有按点分组，结果只有一个全局最短值。
解题步骤
- 用
p1、p2两个别名自连接Point2D。- 按 x、y 字典序只保留一个方向的不同点对。
- 计算距离并取最小值。
- 保留两位小数，设置结果列名。
代码实现
SELECT ROUND(
-- ROUND 套在 MIN 外面：先取精确最小值，最后一次性格式化。
MIN(SQRT(POW(p1.x - p2.x, 2) + POW(p1.y - p2.y, 2))),
2
) AS shortest
FROM Point2D p1
JOIN Point2D p2
-- 严格字典序：既排除「点与自己配对」，又保证每对点只出现一次。
-- 后半段不可省，否则所有横坐标相同的竖直点对都会被丢掉。
ON (p1.x < p2.x) OR (p1.x = p2.x AND p1.y < p2.y);
复杂度分析
- 时间复杂度：按点对枚举的执行方式为 $O(n²)$，具体执行成本取决于查询计划。
- 空间复杂度：MIN 本身仅需常数状态，其他连接或物化工作空间由执行计划决定。
关键点总结
[!green]
- 同 x 的点也可能构成最近点对。
- 严格顺序同时排除自身配对与反向重复。
- 输出是全局最短值，不是按点或坐标分组的结果。
易错点总结
[!yellow]
- 连接不排除自身：零距离污染最小值。
- 条件只有 x 小于：遗漏竖直点对。
- 使用曼哈顿距离：计算的不是题目要求的欧氏距离。
- 增加 GROUP BY：输出粒度发生改变。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 613. 直线上的最近距离 | 简单 | 原题点在一维线上，排序相邻差即可，本题二维点对需比较欧氏距离。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！