难度: Medium
Submission
运行时间: 37 ms
内存: 20.2 MB
class Solution:
def isReflected(self, points: List[List[int]]) -> bool:
# 纵坐标一加一减为零且必须意义对应 计数即可 对应横坐标
l = float('inf')
r = -float('inf')
seen = set()
for x, y in points:
l = min(l, x)
r = max(r, x)
seen.add((x, y))
m = (l + r) / 2
for ele in seen:
x, y = ele
if ((2 * m - x), y) not in seen:
return False
return True
Explain
此题解的思路是通过找到所有给定点集的最左和最右的x坐标值，然后计算这两个x值的中点作为可能的对称轴。之后，遍历每一个点，检查其关于中点的对称点是否存在于点集中。如果所有点都符合这一条件，说明点集关于该中线对称；如果任一点的对称点不存在，则不对称。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def isReflected(self, points: List[List[int]]) -> bool:
# 初始化最左和最右的x坐标值
l = float('inf')
r = -float('inf')
# 创建集合存储点，以便快速检查点的存在性
seen = set()
# 遍历所有点，更新最左和最右x坐标值，同时将点添加到集合中
for x, y in points:
l = min(l, x)
r = max(r, x)
seen.add((x, y))
# 计算可能的对称轴x坐标
m = (l + r) / 2
# 检查每个点的对称点是否也在集合中
for ele in seen:
x, y = ele
if ((2 * m - x), y) not in seen:
return False
# 如果所有点的对称点都在集合中，则返回True
return True
Explore
在处理非常大的点集时，确实可能出现精度问题，尤其是在使用浮点数进行中点计算时。由于浮点数的精度限制，当x坐标的数值非常大或非常接近时，计算中点可能导致轻微的偏差，影响后续的对称性检查。一种可能的解决方案是使用整数运算代替浮点运算。例如，可以将中点计算公式改为使用整数除法 `(l + r) // 2` 或者维持 `(l + r) / 2` 但在检查对称点时四舍五入到最接近的整数。这样可以减少由浮点数引入的误差。
实际上，题解中确实考虑了y坐标的对称性。在检查每个点的对称点是否存在于集合中时，对称点的计算包括了y坐标（即检查点 `(2 * m - x, y)` 是否存在）。这意味着对于每个点 `(x, y)`，不仅x坐标需要对称，y坐标也必须完全相同。因此，题解已经确保了在x轴和y轴上都进行了对称性检查，这是检查点集是否关于某一垂直线对称的正确方法。
在题解的实现中，如果点集为空，应该返回True，因为从集合论的角度看，空集是对称的。同样，如果所有点的x坐标相同，也应该返回True，因为所有这些点本质上都位于同一垂直线上，自然是对称的。当前的代码对于这两种情况都能正确处理：1) 空集情况下，`seen` 集合为空，不进入检查循环，直接返回True；2) 所有点x坐标相同的情况下，计算的中点 `m` 将与所有点的x坐标相同，因此对称点检查始终成立，也将返回True。
如果点集中存在重复的点，题解中的方法仍然能够正确判断对称性。这是因为重复的点在加入 `seen` 集合时自动去重，每个点位置只记录一次。检查对称性时，由于考虑的是位置而非点的个数，所以即便有重复点，只要每个点的对称点也存在于集合中，就能正确地判断出对称性。因此，无需修改代码来特别处理重复点。