Google
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. 1.
    如果存在一条线评分所有点,那么一个点和它关于这条线对称的点的x(横坐标值)和y(纵坐标)的值的和是一样的,包括最大和最小值,由于要求的是这个平分点的线是垂直于x轴的,所以我们只关心点的x值即可
  2. 2.
    找出所有点中x值最大和最小的值,得到它们的和sum
  3. 3.
    将每个点都以 x + "#" + y的形式计算它们的hashcode放入set里
  4. 4.
    再一次遍历所有点,如果当前的点所对应的点 sum - x + "#" + y不在set里,说明不存在一条平分所有点的线
(1) HashTable
1
class Solution {
2
public boolean isReflected(int[][] points) {
3
int min = Integer.MAX_VALUE;
4
int max = Integer.MIN_VALUE;
5
Set<String> set = new HashSet<>();
6
7
for (int[] point : points) {
8
max = Math.max(max, point[0]);
9
min = Math.min(min, point[0]);
10
String code = point[0] + "#" + point[1];
11
set.add(code);
12
}
13
14
int sum = min + max;
15
for (int[] point : points) {
16
String code = (sum - point[0]) + "#" + point[1];
17
if (!set.contains(code)) {
18
return false;
19
}
20
}
21
return true;
22
}
23
}
Copied!

3. Time & Space Complexity

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