356 Line Reflection

356. Line Reflection

1. 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:

Givenpoints=[[1,1],[-1,1]], returntrue.

Example 2:

Givenpoints=[[1,1],[-1,-1]], returnfalse.

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

2. Implementation

思路:

1. 如果存在一条线评分所有点，那么一个点和它关于这条线对称的点的x(横坐标值)和y(纵坐标)的值的和是一样的，包括最大和最小值，由于要求的是这个平分点的线是垂直于x轴的，所以我们只关心点的x值即可

2. 找出所有点中x值最大和最小的值，得到它们的和sum

3. 将每个点都以 x + "#" + y的形式计算它们的hashcode放入set里

4. 再一次遍历所有点，如果当前的点所对应的点 sum - x + "#" + y不在set里，说明不存在一条平分所有点的线

(1) HashTable

class Solution {
    public boolean isReflected(int[][] points) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        Set<String> set = new HashSet<>();

        for (int[] point : points) {
            max = Math.max(max, point[0]);
            min = Math.min(min, point[0]);
            String code = point[0] + "#" + point[1];
            set.add(code);
        }

        int sum = min + max;
        for (int[] point : points) {
            String code = (sum - point[0]) + "#" + point[1];
            if (!set.contains(code)) {
                return false;
            }
        }
        return true;
    }
}

3. Time & Space Complexity

HashTable: 时间复杂度O(n), 空间复杂度O(n)