【力扣（LeetCode）】数据挖掘面试题0003： 356. 直线镜像

题目描述

在一个二维平面空间中，给你 n 个点的坐标。

问，是否能找出一条平行于 y 轴的直线，让这些点关于这条直线成镜像排布？

平行于y轴的直线（即垂直于x轴的直线，其方程形式为( x = a )，其中( a )为常数）的对称点具有以下显著特点：

坐标变化规律

设直线为( x = a )，平面内任意一点( P(x, y) )关于该直线的对称点为( P’(x’, y’) )，则两者坐标满足：

• 纵坐标不变：( y’ = y )（因为对称线平行于y轴，垂直方向无偏移）；
• 横坐标对称：两点的横坐标到直线( x = a )的距离相等，且在直线两侧，即( a - x = x’ - a )，化简得( x' = 2a - x )。

示例：点( (1, 3) )关于直线( x = 2 )的对称点为( (2×2 - 1, 3) = (3, 3) )。

解题方案

• C++ 版本
  • 存储坐标点
  • 找最大、最小边界，计算对称轴
  • 循环遍历，通过当前x，计算对称的x1，判断x1及对应的y是否在坐标点集合中

class Solution {
public:// 判断点集是否能沿某条垂直于x轴的直线对称bool isReflected(vector<pair<int, int>>& points) {// 存储每个x坐标对应的所有y坐标集合std::unordered_map<int, std::set<int>> m;// 记录最大和最小的x坐标int max = INT_MIN, min = INT_MAX;// 遍历所有点，找出x坐标的最大和最小值，并将每个点存入哈希表for (auto a : points) {max = std::max(max, a.first);min = std::min(min, a.first);m[a.first].insert(a.second);}// 计算可能的对称轴位置（x坐标的中间值）double y = (double)(max + min) / 2;// 再次遍历所有点，检查每个点关于对称轴的对称点是否存在for (auto a : points) {// 计算对称点的x坐标int t = 2 * y - a.first;// 如果对称点的x坐标不存在，或者该x坐标下没有对应的y坐标if (!m.count(t) || !m[t].count(a.second)) {return false;}}// 所有点的对称点都存在，说明点集对称return true;}
};    

• python 版本

from collections import defaultdictclass Solution:def isReflected(self, points: List[List[int]]) -> bool:if not points:return Truemin_x = float('inf')max_x = float('-inf')# 使用字典存储每个x坐标对应的y坐标集合# 键: x坐标, 值: 该x坐标下所有y坐标的集合coord_map = defaultdict(set)# 遍历所有点，记录最小和最大x坐标# 同时构建坐标映射关系for x, y in points:min_x = min(min_x, x)max_x = max(max_x, x)coord_map[x].add(y)# 计算对称轴的x坐标（浮点数）axis_x = (min_x + max_x) / 2.0# 检查每个点的镜像点是否存在for x, y in points:# 计算镜像点的x坐标（保持y坐标不变）mirror_x = 2 * axis_x - x# 检查镜像点：# 1. 镜像x坐标必须存在于映射中# 2. 镜像点的y坐标必须与当前点的y坐标相同if mirror_x not in coord_map or y not in coord_map[mirror_x]:return Falsereturn True