网站建设初级工程师,win7优化软件,网站页脚怎么做美观,温州华侨职业中等专业学校文章目录1. 题目2. 解题1. 题目
在一个二维平面空间中#xff0c;给你 n 个点的坐标。 问#xff0c;是否能找出一条平行于 y 轴的直线#xff0c;让这些点关于这条直线成镜像排布#xff1f;
示例 1#xff1a;
输入: [[1,1],[-1,1]]
输出: true示例 2#xff1a;
输入…
文章目录1. 题目2. 解题1. 题目
在一个二维平面空间中给你 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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
按x排序相同则按y排序去重前半部分在x基础上按y降序方便双指针比较还要考虑都在一条直线上也是可以的
class Solution {
public:bool isReflected(vectorvectorint 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都相等在一条线上truereturn 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(vectorvectorint 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;setvectorint s(points.begin(), points.end());for(auto p : points)if (s.find({xmid-p[0], p[1]}) s.end())return false;return true;}
};我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
