在一个二维平面空间中,给你 n 个点的坐标。 问,是否能找出一条平行于 y 轴的直线,让这些点关于这条直线成镜像排布?
示例 1:
输入: [[1,1],[-1,1]]
输出: true
示例 2:
输入: [[1,1],[-1,-1]]
输出: false
拓展:
你能找到比 O(n^2) 更优的解法吗?
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/line-reflection 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
bool isReflected(vector<vector<int>>& points) {
sort(points.begin(), points.end(),[&](auto a, auto b){
if(a[0] == b[0])
return a[1] < b[1];//y大的靠后
return a[0] < b[0];//按x坐标排序
});
if(points[0][0] == points[points.size() - 1][0])//x都相等,在一条线上,true
return true;
points.erase(unique(points.begin(), points.end()), points.end());//有重复的点
int half = points.size()/2;
sort(points.begin(), points.begin()+half, [&](auto a, auto b){
if(a[0] == b[0])
return a[1] > b[1];//前半部分y大的靠前
return a[0] < b[0];//按x坐标排序
});
int l = 0, r = points.size()-1;
if(points[l][1] != points[r][1]) return false;
int xmid = points[l++][0] + points[r--][0];//中心的两倍
while(l < r)
{
if(points[l][0] != points[r][0] && (points[l][1] != points[r][1]
|| points[l][0] + points[r][0] != xmid)) return false;
l++,r--;
}
return points[l][0] + points[r][0] == xmid;
}
};
// [[1,1],[0,1],[-1,1],[0,0]]
// [[1,2],[2,2],[1,4],[2,4]]
// [[-16,1],[16,1],[16,1]]
// [[1,1],[-1,1]]
// [[0,0],[0,-1]]
// [[0,0],[1,0],[3,0]]
参考大力王的简洁写法:
class Solution {
public:
bool isReflected(vector<vector<int>>& points) {
int left = INT_MAX, right = INT_MIN;
for(auto& p : points)
{
left = min(p[0], left);
right = max(p[0], right);
}
int xmid = left + right;
set<vector<int>> s(points.begin(), points.end());
for(auto& p : points)
if (s.find({xmid-p[0], p[1]}) == s.end())
return false;
return true;
}
};