LeetCode 612. 平面上的最近距离

Categories:

题目描述
思路分析
1. 解法一：SQL 自连接（推荐）
相似题目

题目描述

✅ 612. 平面上的最近距离

思路分析

解法一：SQL 自连接（推荐）

核心思路：

对 point 表进行自连接，枚举所有点对 (p1, p2)，用条件 p1.x < p2.x OR (p1.x = p2.x AND p1.y < p2.y) 避免重复计算

计算两点欧氏距离的平方，取 SQRT 后保留两位小数

使用 MIN 聚合取最小值

复杂度分析：

时间复杂度：O(n²)，其中 n 表示表中点的数量，自连接枚举所有点对

空间复杂度：O(n²)，自连接结果集大小

SELECT ROUND(
    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);

相似题目

题目	难度	考察点
610. 判断三角形	简单	SQL、数学
577. 员工奖金	简单	SQL、连接
586. 订单最多的客户	简单	SQL、聚合
607. 销售员	简单	SQL、子查询
614. 二级关注者	中等	SQL、自连接
619. 只出现一次的最大数字	简单	SQL、聚合

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/50066874