Line Reflection.java

M
1531928255
tags: Hash Table, Math
time: O(n)
space: O(n)

给一串点, 找是否有一个所有点中间的, 跟y-axis平行的中线.

#### Hash Table
- 1. store in `Map<y, set<x>>`, 2. iterate over map, check head,tail against the mid point
- 很好的细节题目:
- 1. 除以2, 需要存double
- 2. (问面试官)可以有重复的点! 所以track `set<x>`
- 3. 处理 left==right时候, 就当做两个点来处理.
- 4. 存进set里面没有sort, 但是最后做check的时候, 需要sort list
- 时间: visit all nodes 两遍,  O(n)

```
/*
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)?

Credits:
Special thanks to @memoryless for adding this problem and creating all test cases.
*/

/*
line parrel to y-axis: for all points with same y, all head/tail should have same mid point
1. store in Map<y, list<x>>
2. iterate over map, check head,tail mid
*/
class Solution {
    public boolean isReflected(int[][] points) {
        if (points == null || points.length == 0 || points[0] == null || points[0].length == 0) return true;
        
        Map<Integer, Set<Double>> map = new HashMap<>();
        for (int[] point : points) {
            map.putIfAbsent(point[1], new HashSet<>());
            map.get(point[1]).add((double)point[0]);
        }
        
        List<Double> sampleRow = new ArrayList<>(map.get(points[0][1]));
        Collections.sort(sampleRow);
        double mid = (sampleRow.get(0) + sampleRow.get(sampleRow.size() - 1)) / 2;
        
        for (Set<Double> row: map.values()) {
            int left = 0, right = row.size() - 1;
            List<Double> sortedRow = new ArrayList<>(row);
            Collections.sort(sortedRow);
            while (left <= right) {
                if ((sortedRow.get(left) + sortedRow.get(right)) / 2 != mid) {
                    return false;
                }
                left++;
                right--;
            }
        }
        return true;
    }
}
```