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

560 Subarray Sum Equals K

748 Shortest Completing Word

Last modified 2yr ago

Copy link

Contents

356. Line Reflection

1. Question

2. Implementation

3. Time & Space Complexity

356. Line Reflection​

1. Question

2. Implementation

3. Time & Space Complexity

356. Line Reflection