356. Line Reflection

发表于 | 分类于

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

解法1：O(N) Time + O(N) Space

这题的题意是对于N个给定的点，找一下是否存在一条平行与y轴的线，使得所有点都对称与此条线。
那么怎么确定这条平行的线是关键。
如果点都是对称存在的，那么最左面的点和最右面的点当中的线就是平行于y轴的对称线。所有其他的点都必须以此为基准。
用一个set存储每一个点，并且找出最左最右两个点。找出以后，对于每一个点，检查他的对称点是否在set中。
放入set的时候用到了Arrays.hashCode(int[])的function。
C++

1

Java

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
public class Solution {
    public boolean isReflected(int[][] points) {
        if (points == null || points.length == 0) {
            return true;
        }
        HashSet<Integer> set = new HashSet<>();
        int xmin = Integer.MAX_VALUE, xmax = Integer.MIN_VALUE;
        for (int[] point : points) {
            xmin = Math.min(xmin, point[0]);
            xmax = Math.max(xmax, point[0]);
            set.add(Arrays.hashCode(point));
        }
        int sum = xmin + xmax;
        for (int[] point : points) {
            if (!set.contains(Arrays.hashCode(new int[] { sum - point[0], point[1]}))) {
                return false;
            }
        }
        return true;
    }
}