README.md

356. 直线镜像

English Version

题目描述

在一个二维平面空间中，给你 n 个点的坐标。问，是否能找出一条平行于 y 轴的直线，让这些点关于这条直线成镜像排布？

注意：题目数据中可能有重复的点。

 

示例 1：

输入：points = [[1,1],[-1,1]]
输出：true
解释：可以找出 x = 0 这条线。

示例 2：

输入：points = [[1,1],[-1,-1]]
输出：false
解释：无法找出这样一条线。

 

提示：

• n == points.length
• 1 <= n <= 10^4
• -10^8 <= points[i][j] <= 10^8

 

进阶：你能找到比 O(n²) 更优的解法吗?

解法

先找出所有点中的最小、最大的 x 坐标 minX 和 maxX。若存在满足条件的直线，则直线 x = (minX + maxX) / 2。(或者说：s = minX + maxX)

遍历每个点 point(x, y)，若 (s - x, y) 不在点集里，说明不满足条件，直接返回 false。遍历结束返回 true。

Python3

class Solution:
    def isReflected(self, points: List[List[int]]) -> bool:
        min_x, max_x = inf, -inf
        point_set = set()
        for x, y in points:
            min_x = min(min_x, x)
            max_x = max(max_x, x)
            point_set.add((x, y))
        s = min_x + max_x
        for x, y in points:
            if (s - x, y) not in point_set:
                return False
        return True

Java

class Solution {
    public boolean isReflected(int[][] points) {
        int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE;
        Set<String> pointSet = new HashSet<>();
        for (int[] point : points) {
            minX = Math.min(minX, point[0]);
            maxX = Math.max(maxX, point[0]);
            pointSet.add(point[0] + "." + point[1]);
        }
        long s = minX + maxX;
        for (int[] point : points) {
            if (!pointSet.contains((s - point[0]) + "." + point[1])) {
                return false;
            }
        }
        return true;
    }
}

...