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],[2,2],[-2,2]], return true.

Example 2: Given points = [[1,1],[-1,-1]], return false.

Follow up: Could you do better than O(n2)?

Hint

Find the smallest and largest x-value for all points. If there is a line then it should be at y = (minX + maxX) / 2. For each point, make sure that it has a reflected point in the opposite side.

Train of Thought

用map存点的y轴为key, x坐标为value, 一个个点去找有没有对称的

optimize: 假设对称轴横坐标为x, 任意两个对称点, x1 - x = x - x2, x1 + x2 = 2x, 因为对称轴是不变的,两个点的x坐标的和必然等于minX + maxX

Code

public boolean isReflected(int[][] points) {
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    HashSet<String> set = new HashSet<>();
    for(int[] p:points){
        max = Math.max(max,p[0]);
        min = Math.min(min,p[0]);
        String str = p[0] + "a" + p[1];
        set.add(str);
    }
    int sum = max+min;
    for(int[] p:points){
        //int[] arr = {sum-p[0],p[1]};
        String str = (sum-p[0]) + "a" + p[1];
        if( !set.contains(str))
            return false;

    }
    return true;
}

Complexity