LeetCode 612. 平面上的最近距离

2021-09-08 HGNULB 约 10 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 612. 平面上的最近距离

题意分析

表里每行是平面上的一个点，含 x、y 两个坐标。要求算出任意两个不同点之间的最短欧氏距离，结果保留两位小数。

先明确输出粒度：结果是一行一列的标量——整张表汇总出一个最小值，而不是每个点一行。这决定了最终必然要用聚合函数 MIN，且不带任何 GROUP BY。

核心难点在于 SQL 没有「两两组合」这个原生概念。要枚举所有点对，唯一的办法是把表和自己连接——FROM Point2D p1 JOIN Point2D p2，连接结果的每一行就是一个点对。这是自连接最典型的用途：把「行与行之间的关系」变成「同一行里的两组列」，从而能在 SELECT 里同时引用两个点的坐标。

但无条件自连接会产生三类不该要的行。第一，每个点与自己配对（p1 和 p2 是同一行），距离为 0，会让答案恒等于 0。第二，同一对点被数两次（(A, B) 和 (B, A)），虽然距离相同不影响 MIN 的结果，但白白多算一倍。既然要排除自己配自己，最省事的办法就是给点对施加一个严格的顺序，一举把这两类都挡掉。

顺序怎么定？不能只写 p1.x < p2.x——那样会把所有横坐标相同的点对全部丢掉。正确做法是用字典序：先比 x，x 相等时再比 y。这个条件对任意两个不同点恰好成立一次（要么 p1 在前，要么 p2 在前），既去重又排除自配。

约束方面，点数不大，$O(n^2)$ 的笛卡尔积完全可以接受。题目也没有别的路可走——SQL 层面无法表达「分治求最近点对」那种 $O(n \log n)$ 的算法。

边界：题目保证所有点互不相同，所以不存在距离为 0 的合法点对；ROUND(..., 2) 是题目明文要求的输出格式，不能省；结果列的别名要写成 shortest。

解法：SQL 自连接枚举点对

核心思路

问题拆成三步：枚举所有点对 → 算出每对的距离 → 取最小值。SQL 里这三步分别对应自连接、SELECT 表达式、聚合函数，结构非常清晰。

第一步，自连接。FROM Point2D p1 JOIN Point2D p2 让同一张表以两个别名参与连接，结果集的每一行同时持有两个点的坐标。别名是必需的——没有它就无法在表达式里区分「哪个 x」。

第二步，去重与排除自配。如果连接条件为空（纯笛卡尔积），n 个点会产生 $n^2$ 行，其中 n 行是自己和自己（距离 0），剩下的每一对都出现两次。距离 0 会直接污染 MIN，必须排除。

排除的方式有两种。一种是按主键或坐标写「不相等」条件，但「不相等」只排掉自配、不去重；另一种是施加严格的全序，一次解决两个问题。这里用字典序：p1.x < p2.x OR (p1.x = p2.x AND p1.y < p2.y)。对任意两个不同点，这个条件在两种排列中恰好成立一次；而 p1 与 p2 是同一点时，x 相等且 y 相等，两个分支都不成立，自然被排除。

为什么不能只写 p1.x < p2.x？因为竖直方向上的点对（x 相同、y 不同）会被整个丢掉，最短距离恰好出现在这类点对上时答案就错了。这是本题最典型的陷阱——补上 OR (p1.x = p2.x AND p1.y < p2.y) 这一段才是完整的字典序。

第三步，距离与聚合。欧氏距离是 $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$，写成 SQRT(POW(p1.x - p2.x, 2) + POW(p1.y - p2.y, 2))。把它套在 MIN(...) 里，对整个连接结果求最小值；因为没有 GROUP BY，聚合作用于全表，输出恰好一行。最外层再套 ROUND(..., 2) 满足输出格式。

注意 ROUND 要套在 MIN 外面而不是里面。套在里面是「先把每对距离四舍五入再取最小」，虽然在本题的数据下结果通常相同，但语义上是先损失精度再比较，两个距离在第三位小数上分出胜负时就会选错点对。先求精确最小值、最后一次性格式化，才是正确的顺序。

不变量式的说法：连接结果的每一行恰好对应一对互不相同的点，且每对只出现一次。只要这个性质成立，MIN 的作用域就正好是全体点对，答案不多不少。

解题步骤

用两个别名 p1、p2 对同一张表做自连接。为什么：SQL 无法在一行内直接引用「另一行」，只有把表和自己连起来，才能让两个点的坐标出现在同一行、供同一个表达式使用；别名是区分二者的唯一手段。

在连接条件里写 p1.x < p2.x OR (p1.x = p2.x AND p1.y < p2.y)。为什么：这是一个严格的字典序。它同时完成两件事——排除「点与自己配对」（同一行两个坐标都相等，两个分支都不成立）和「同一对点出现两次」（(A,B) 与 (B,A) 里只有一个满足）。少写 OR 后半段会丢掉所有 x 相同的竖直点对；改成 <> 之类的不等条件则只解决自配、不去重。

括号要把 AND 那一段包住。为什么：AND 的优先级高于 OR，不加括号时表达式的含义恰好一致，但显式括号让「字典序」的意图一目了然，也避免日后修改条件时被优先级坑到。

用 SQRT(POW(p1.x - p2.x, 2) + POW(p1.y - p2.y, 2)) 计算距离。为什么：这是欧氏距离的直接翻译；用 POW(..., 2) 而不是把差值写两遍相乘，可读性更好，也不易漏掉某个坐标。

外层套 MIN(...) 且不写 GROUP BY。为什么：题目要的是全局最短距离这一个标量；不带分组时聚合作用于整个结果集，恰好输出一行一列，与要求的输出粒度一致。

最外层套 ROUND(..., 2) 并起别名 shortest。为什么：题目明确要求保留两位小数、且结果列名固定；ROUND 必须在 MIN 外面——先取精确最小值再格式化，避免「先舍入再比较」在第三位小数处选错点对。

走一遍一份具体数据。设表中有三个点：(-1, -1)、(0, 0)、(-1, -2)。

自连接产生 $3 \times 3 = 9$ 行，逐行检查字典序条件（记 A = (-1,-1)、B = (0,0)、C = (-1,-2)）：

(A, A)：x 相等且 y 相等，两个分支都不成立，排除——这正是排除自配的机制。

(A, B)：-1 < 0 成立，保留。距离 $\sqrt{1 + 1} \approx 1.4142$。

(A, C)：x 都是 -1，第一个分支不成立；第二个分支要求 p1.y < p2.y 即 -1 < -2，不成立，排除。

(B, A)：0 < -1 不成立；x 不相等所以第二个分支也不成立，排除——(A, B) 已经被数过一次，这里正是去重在起作用。

(B, B)：自配，排除。

(B, C)：0 < -1 不成立，x 不等，排除（(C, B) 会被保留）。

(C, A)：x 都是 -1，第二分支 -2 < -1 成立，保留。距离 $\sqrt{0 + 1} = 1.0$。

(C, B)：-1 < 0 成立，保留。距离 $\sqrt{1 + 4} \approx 2.2361$。

(C, C)：自配，排除。

最终参与聚合的恰好是三对点，正好是 $C_3^2 = 3$ 对，一个不多一个不少。MIN 取到 1.0，ROUND(1.0, 2) 得 1.00。

特别看 (C, A) 这一对：它的两个点横坐标完全相同，只能靠字典序的第二分支才被保留下来，而它恰恰是距离最短的那一对。若连接条件只写 p1.x < p2.x，这一对会被整个丢掉，答案会错成 1.41——这就是必须写完整字典序的直接理由。

代码实现

SELECT ROUND(
    -- ROUND 套在 MIN 外面：先取精确最小值，最后一次性格式化。
    MIN(SQRT(POW(p1.x - p2.x, 2) + POW(p1.y - p2.y, 2))),
    2
) AS shortest
FROM point_2d p1
JOIN point_2d p2
-- 严格字典序：既排除「点与自己配对」，又保证每对点只出现一次。
-- 后半段不可省，否则所有横坐标相同的竖直点对都会被丢掉。
ON (p1.x < p2.x) OR (p1.x = p2.x AND p1.y < p2.y);

复杂度分析

时间复杂度：$O(n^2)$，n 为点数。凭什么：自连接在没有可用索引的等值条件时只能走嵌套循环，产生 $n^2$ 个候选行；每行做一次字典序判断、一次开方与两次乘方，都是常数代价；最后的 MIN 是对不超过 $n^2 / 2$ 行的一趟线性扫描。连接条件是范围比较而非等值，无法借助哈希连接把量级降下来，所以平方是这类「两两配对」SQL 的固有代价。

空间复杂度：$O(1)$ 到 $O(n^2)$，取决于执行计划。凭什么：MIN 本身只需一个累加器，若引擎采用流式聚合（边连接边更新最小值）则额外空间是常数；但若优化器选择先物化连接结果再聚合，中间结果集可达 $O(n^2)$ 行。表本身占 $O(n)$。

关键点总结

SQL 里表达「两两组合」的唯一手段是自连接：把表以两个别名连起来，行与行的关系就变成了同一行内的两组列。凡是遇到「任意两个……之间」的措辞，先想自连接。

自连接必须处理两个副作用：自己配自己和同一对出现两次。用一个严格全序条件（字典序、或主键 id1 < id2）可以一次解决两者，比写 <> 再另想办法去重干净得多。

格式化要放在聚合之外。ROUND(MIN(...)) 与 MIN(ROUND(...)) 的语义不同：后者先损失精度再比较，两个候选在被舍弃的位数上分胜负时会选错。凡是「先算再格式化」的需求，都要检查函数的嵌套顺序。

先钉死输出粒度再动手：本题输出是一行一列的标量，所以聚合不带 GROUP BY；如果题目改成「每个点到最近邻居的距离」，粒度变成每点一行，就必须加 GROUP BY p1.id 了。

$O(n^2)$ 在这里是可接受的，也是 SQL 层面能做到的极限——平面最近点对的 $O(n \log n)$ 分治算法无法用声明式 SQL 表达。能主动说明「为什么这里只能平方」，比默默写出平方解法更有说服力。

面试延伸：被问「如果点数上百万怎么办」时，方向是先做空间剪枝再算距离——按网格把平面分块（FLOOR(x / d)、FLOOR(y / d) 作为桶键），只对同桶及相邻桶内的点做自连接；或者在应用层用 KD 树 / R 树索引，把候选对数从 $n^2$ 降到近似线性。

易错点总结

连接条件只写 p1.x < p2.x：点集 (-1,-1)、(-1,-2)、(0,0) → 横坐标相同的那对（距离 1.00）被整个丢掉，返回 1.41，正确答案是 1.00。

完全不写连接条件（纯笛卡尔积）：任意点集 → 每个点与自己配对产生距离 0，MIN 恒为 0.00。

只写 p1.x <> p2.x OR p1.y <> p2.y 之类的不等条件：排除了自配但没去重 → 每对点被算两次；结果虽然仍正确，但连接结果规模翻倍，且一旦后续要 COUNT 点对数就会错一倍。

ROUND 写在 MIN 里面：两对点的距离分别是 1.0049 和 1.0051 → 先舍入都变成 1.00，虽然本例结果相同，但当两者分别为 1.004 与 1.006 且题目要求更高精度时就会选错来源；语义上先损失精度再比较是错的。

忘记 ROUND(..., 2)：结果输出 1.4142135623731 → 与期望的 1.41 格式不符，判题直接失败。

结果列没起别名或别名拼错：期望列名是 shortest → 列名不匹配，判题失败。

给聚合加了 GROUP BY：例如 GROUP BY p1.x → 输出变成每个横坐标一行，而题目要的是全表一个标量。

用 ABS(p1.x - p2.x) + ABS(p1.y - p2.y) 计算距离：把欧氏距离写成了曼哈顿距离 → 点 (0,0) 与 (1,1) 算出 2 而非 1.41，全盘错误。

POW 的指数写成 p1.x - p2.x：把「平方」误写成「以差为指数」→ 表达式恒错，且不会报语法错误，非常隐蔽。

假设表中不存在重复点却在有重复点的数据上运行：两个坐标完全相同的点 → 字典序条件对它们两个分支都不成立，这一对被排除，距离 0 不会出现；若题目语义要求把重复点视为「距离 0 的两个点」，就需要改用 id 做顺序键。

相似题目

题目	难度	考察点
197. 上升的温度	简单	同为单表自连接，但连接条件是「日期相差一天」，考日期函数而非顺序去重
181. 超过经理收入的员工	简单	自连接的连接键是外键指向自身，配对关系由数据决定而非全组合
182. 查找重复的电子邮箱	简单	找相同项可以用分组代替自连接，正好对照「什么时候不必两两配对」
570. 至少有5名直接下属的经理	中等	同为自引用表，但用 `GROUP BY` + `HAVING` 统计，输出粒度是每位经理一行
176. 第二高的薪水	中等	同为单标量输出，难点在无结果时要返回 `NULL` 而非空集
184. 部门工资最高的员工	中等	聚合后需回连原表取明细，粒度从「每组一行」变回「每行一条记录」
569. 员工薪水中位数	困难	同样需要组内定位，但用窗口函数排名代替自连接，复杂度从平方降到 $O(n \log n)$
178. 分数排名	中等	经典的「自连接计数模拟排名」题，可对照理解自连接的平方代价与窗口函数的优势