Star

Leetcode 356. Line Reflection

Posted on | In |

Question:

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)?

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.

Explanation:

刚开始的思路是， 用一个map存{y值:[所有相应x值]}。 对于每一个y值，将其对应的x值的list排序。用two pointers检查是不是对称。 这样的复杂度超过O(n^2)了，sort就已经O(nlogn)了。 于是，按照了hint写，先遍历一遍，得到x最大值和最小值，从而得到x中间值。再遍历一遍，存下每个点的对称点。最后遍历一遍，如果有哪个坐标不在set里面，说明没有对称点。（和two sum一样的思路）

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public boolean isReflected(int[][] points) {
    if(points == null || points.length == 0) return true;
    int minX = Integer.MAX_VALUE;
    int maxX = Integer.MIN_VALUE;
    double midX = 0.0;
    for( int i=0; i<points.length; i++) {
        int[] point = points[i];
        int x = point[0]; int y = point[1];
        minX = Math.min(minX, x);
        maxX = Math.max(maxX, x);
    }
    midX = (minX + maxX) / 2.0;
    HashSet<Integer> set = new HashSet<>();
    for( int i=0; i<points.length; i++) {
        int[] point = points[i];
        int x = point[0]; int y = point[1];
        int[] reflect = new int[2];
        reflect[0] = (int)(2*midX- x);
        reflect[1] = y;
        set.add(Arrays.hashCode(reflect));
    }
    for( int i=0; i<points.length; i++) {
        int[] point = points[i];
        if (!set.contains(Arrays.hashCode(point))) return false;
    }
    return true;
}