[leetcode] 939. Minimum Area Rectangle

[leetcode] 939. Minimum Area Rectangle

Description

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]Output: 4

Example 2:

Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]Output: 2

Note:

1 <= points.length <= 5000 <= points[i][0] <= 400000 <= points[i][1] <= 40000All points are distinct.

分析

题目的意思是：求给定数组的坐标所构成的最小的矩形的面积。我参考了一下答案的思路，首先确定对角线上的两个点，然后判断其他两个点是否在给定的坐标集合里，就可以判断四个坐标能否构成一个矩形。

这里把points变成了集合S，主要是直接判断坐标在points列表里面ac不了，所以才进行了转换。两层循环，列举对角线的坐标，然后判断剩下的坐标是否在坐标集合里面，如果符合条件，则维护最小面积res，否则就继续遍历了。

代码

class Solution: def minAreaRect(self, points: List[List[int]]) -> int: res=float('inf') n=len(points) S=set(map(tuple,points)) for i in range(n): for j in range(i): p1=points[i] p2=points[j] if(p1[0]!=p2[0] and p1[1]!=p2[1]): if((p1[0],p2[1]) in S and (p2[0],p1[1]) in S): res=min(res,abs(p1[0]-p2[0])*abs(p1[1]-p2[1])) if(res==float('inf')): return 0 return res

参考文献

​​solution​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。