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($n^2$)?

Hint:

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

题意是给出很多点，看有没有一个平行于y轴的线让所有的点关于这个线对称。在坐标轴上这个线其实就是 x = a，a可以为任意数.

  1. 提示给的很好，先找出所有点(x, y)中x的最大值maxX和最小值minX
  2. 如果有一个对称线，那这个线一定是 x = (maxX + minX) / 2。 提示给的是 y = ?，不够严谨，是错误的。
  3. 如何找一个点的对称点？如果(x1, y1), (x2, y2)，关于x = a对称，说明 y1 = y2, (x1 + x2) / 2 = a. 因为a = (maxX + minX) / 2， 所以 x2 = maxX + minX - x1.
  4. 先遍历一所有点，把所有点放到HashSet里。然后在遍历一遍所有点，求出相应的对称点。如果对称点不在HashSet里，说明找不到对称轴。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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] + "" + p[1];
        set.add(str);
    }
    int sum = max + min;
    for (int[] p : points) {
        String str = (sum - p[0]) + "" + p[1];
        if (!set.contains(str))
            return false;
    }
    return true;
}