[LeetCode] Line Reflection 直线对称-白红宇

[LeetCode] Line Reflection 直线对称

阅读量：6235 次

发布时间：2019-06-22

本文共 1699 字，大约阅读时间需要 5 分钟。

Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given set of 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²)?

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.

Credits:

Special thanks to for adding this problem and creating all test cases.

这道题给了我们一堆点，问我们存不存在一条平行于y轴的直线，使得所有的点关于该直线对称。题目中的提示给的相当充分，我们只要按照提示的步骤来做就可以解题了。首先我们找到所有点的横坐标的最大值和最小值，那么二者的平均值就是中间直线的横坐标，然后我们遍历每个点，如果都能找到直线对称的另一个点，则返回true，反之返回false，参见代码如下：

解法一：

class Solution {public:    bool isReflected(vector
     
      
       >& points) {        unordered_map

> m; int mx = INT_MIN, mn = INT_MAX; for (auto a : points) { mx = max(mx, a.first); mn = min(mn, a.first); m[a.first].insert(a.second); } double y = (double)(mx + mn) / 2; for (auto a : points) { int t = 2 * y - a.first; if (!m.count(t) || !m[t].count(a.second)) { return false; } } return true; }};

下面这种解法没有求最大值和最小值，而是把所有的横坐标累加起来，然后求平均数，基本思路都相同，参见代码如下：

解法二：

class Solution {public:    bool isReflected(vector
     
      
       >& points) {        if (points.empty()) return true;        set
       
        
         > pts;        double y = 0;        for (auto a : points) {            pts.insert(a);            y += a.first;        }        y /= points.size();        for (auto a : pts) {            if (!pts.count({y * 2 - a.first, a.second})) {                return false;            }        }        return true;    }};

类似题目：

参考资料：

转载地址：http://keqna.baihongyu.com/

你可能感兴趣的文章