LeetCode刷题实战356：直线镜像-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 直线镜像，我们先来看题面：

https://leetcode-cn.com/problems/russian-doll-envelopes/

Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points.

在一个二维平面空间中，给你 n 个点的坐标。

问，是否能找出一条平行于 y 轴的直线，让这些点关于这条直线成镜像排布？

示例

示例 1：
输入: [[1,1],[-1,1]]
输出: true

示例 2：
输入: [[1,1],[-1,-1]]
输出: false
拓展：
你能找到比 O(n^2) 更优的解法吗?

解题

https://blog.csdn.net/weixin_44171872/article/details/108761422

（1）先找出所有的点中最左边和最右边的两个点，使用这两个点确定出临时的中间位置，并以此位置来验证后面的点是否符合要求；

（2）对所有的点进行统计，统计的数据结构使用unordered_map<int,unordered_set< int>>,键使用坐标点的纵坐标，对应的值将统计该纵坐标下，所有的横坐标；

（3）在后面的判断中，找出所有的unordered_set中的元素，其对应的镜像坐标是否存在即可，若出现某个值的镜像坐标不存在，则直接返回false;

class Solution {
public:
    bool isReflected(vector<vector<int>>& points) {
        double average=0.0;//后面作为中间直线坐标的2倍使用
        //找出左右两个值
        int left=INT_MAX;
        int right=INT_MIN;
        //统计元素
        unordered_map<int,unordered_set<int>> mp;
        for(vector<int>& p:points){
            left=min(p[0],left);
            right=max(p[0],right);
            mp[p[1]].insert(p[0]);
        }
        //确定中间位置
        average=left+right;
        for(auto& it:mp){
          //确定对应同一个纵坐标下的所有的横坐标，其对应的镜像点是否存在，若不存在，则直接返回false
            for(int p:it.second){
                if(!it.second.count(average-p)){
                    return false;
                }
            }
        }
        //判断所有的点后，返回true
        return true;
    }
};