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)?
Hint:
Find the smallest and largest x-value for all points.
If there is a line then it should be at y = (minX + maxX) / 2.
For each point, make sure that it has a reflected point in the opposite side.
本题精妙之处在于:1. 如何最快找到possible的line的x axis(我最开始想到要用quickselect find median的方法,结果别人有min max方法)
1 public class Solution {
2 public boolean isReflected(int[][] points) {
3 int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE;
4 HashSet<String> set = new HashSet<>();
5 for (int[] point : points) {
6 minX = Math.min(minX, point[0]);
7 maxX = Math.max(maxX, point[0]);
8 set.add(point[0] + "a" + point[1]);
9 }
10 double sum = minX + maxX;
11 for (int[] point : points) {
12 if (!set.contains((int)(sum-point[0]) + "a" + point[1]))
13 return false;
14 }
15 return true;
16 }
17 }