Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points.
Example 1:
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)?
Python Solution:
class Solution(object):
def isReflected(self, points):
"""
:type points: List[List[int]]
:rtype: bool
"""
if not points: return True
data = collections.defaultdict(set)
for point in points:
data[point[1]].add(point[0])
vals = next(iter(data.values()))
key = min(vals) + max(vals)
for _, vals in data.items():
for val in vals:
if key - val not in vals: return False
return True
class Solution(object):
def isReflected(self, points):
"""
:type points: List[List[int]]
:rtype: bool
"""
if not points: return True
X = min(points)[0] + max(points)[0]
return {(x, y) for x, y in points} == {(X - x, y) for x, y in points}
Summary:
- The first solution is the way C programmer will do.
- The secord solution is much more pythonic, I think.
LeetCode: 356. Line Reflection
近期评论