Line Reflection

https://leetcode.com/problems/line-reflection/description/

Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points.

Example 1:

Given points = [[1,1],[-1,1]], return true.

Example 2:

Given points = [[1,1],[-1,-1]], return false.

Follow up:

Could you do better than O(n2)?

Thoughts

给一堆二维点, 问里头每个点是否都关于同一个与Y轴平行的线对称. 不难想到把x最小和最大的点查出来, 如果那条线存在, 那肯定就是它俩的中点所在的竖线. 正常来说 midX = minX + (maxX - minX) / 2 = (maxX + minX) / 2, 然后对每个x算出反射点refX = 2 mid - x. 如果这是数学题没问题, 但编程有个精度问题, midX很可能不是整数. 但我们真的需要算出midX吗? 求refX只要2 mid就好了, 也就是minX + maxX. 成功避免了精度问题.

还有个小优化就是把点都存成string形式放入HashSet, 代码更简洁.

Code

class Solution {
    public boolean isReflected(int[][] points) {
        int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE;
        Set<String> pts = new HashSet<>();
        for (int[] point : points) {
            minX = Math.min(minX, point[0]);
            maxX = Math.max(maxX, point[0]);
            pts.add(point[0] + "," + point[1]);
        }

        int sum = minX + maxX;
        for (int[] point : points) {
            int refX = sum - point[0];
            if (pts.contains(refX + "," + point[1])) {
                continue;
            }
            return false;
        }

        return true;
    }
}

Analysis

时间复杂度O(N).