LeetCode刷题实战356:直线镜像
Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points.
示例
示例 1:
输入: [[1,1],[-1,1]]
输出: true
示例 2:
输入: [[1,1],[-1,-1]]
输出: false
拓展:
你能找到比 O(n^2) 更优的解法吗?
解题
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;
}
};