356. Line Reflection

2017-08-25  本文已影响0人  Jeanz

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

一刷
题解:一种很简单的思路。先找到那个反射面。所以我们要先找到所有点中x最小的,x最大的,它们的平均值即是反射面sum/2。然后再将所有点p[0] + "a" + p[1]存入set中,如果sum - p[0] + "a" + p[1]不在set中。return false

class Solution {
    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] + "a" + p[1];
            set.add(str);
        }
        int sum = max + min;
        for(int[] p:points){
            String str = (sum-p[0]) + "a" + p[1];
            if( !set.contains(str)) return false;
        }
        return true;
    }
}
上一篇下一篇

猜你喜欢

热点阅读