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:

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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(n2)?

Hint:

  1. Find the smallest and largest x-value for all points.
  2. If there is a line then it should be at y = (minX + maxX) / 2.
  3. For each point, make sure that it has a reflected point in the opposite side.

Credits:
Special thanks to @memoryless for adding this problem and creating all test cases.

给定一个二维平面上的n个点，找出是否有一条平行于y轴的线反映给定的一组点。

例1：

给定点=[[1,1]，[-1,1]]，返回true。

例2：

给定点=[[1,1]，[-1，-1]]，返回false。

跟进：

你能比O（n2）做得更好吗？

提示：

  1. 找出所有点的最小和最大x值。
  2. 如果有一条线，那么它应该是y=（minx+maxx）/2。
  3. 对于每个点，确保在另一侧有一个反射点。

信用：

特别感谢@memoryless添加此问题并创建所有测试用例。

Solution: 

 1 class Solution{
 2     func isReflected(_ points: [[Int]]) -> Bool
 3     {
 4         if points.isEmpty {return true}
 5         var pts:Set<[Int]> = Set<[Int]>()
 6         var y:Double = 0
 7         for a in points
 8         {
 9             pts.insert(a)
10             y += Double(a[0])
11         }
12         y /=  Double(points.count)
13         for a in pts
14         {
15             if !pts.contains([Int(y * 2) - a[0],a[1]])
16             {
17                 return false
18             }
19         }
20         return true
21     }
22 }

点击：Playground测试

1 print(Solution().isReflected( [[1,1],[-1,1]]))
2 //Print true
3 print(Solution().isReflected(  [[1,1],[-1,-1]]))
4 //Print false

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄