Skip to content

Latest commit

 

History

History
140 lines (80 loc) · 3.49 KB

0939._Minimum_Area_Rectangle.md

File metadata and controls

140 lines (80 loc) · 3.49 KB

939. Minimum Area Rectangle

难度: Medium

刷题内容

原题连接

内容描述



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 <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******

最开始的时候我们以x坐标为key，value是所有这个x坐标对应y坐标的set集合

然后我们用竖着扫描的方法,从最小的x坐标开始往右边扫，如果当前x坐标和下一个x坐标的y坐标set的交集有2个或者2个以上，那我们肯定可以组成一个rectangle

如果一直都是len(same) < 2，说明所有的点都组成不了一个rectangle，直接返回0，否则我们每次都算出rectangle的面积，取最小值

class Solution:
    def minAreaRect(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        lookup = collections.defaultdict(set)
        for p in points:
            x, y = p
            lookup[x].add(y)
        x_idxes = sorted(lookup.keys())
        res = sys.maxsize
        flag = False
        for i in range(len(x_idxes)):
            for q in range(i+1, len(x_idxes)):
                same = lookup[x_idxes[i]].intersection(lookup[x_idxes[q]])
                if len(same) < 2:
                    continue
                flag = True
                same = list(same)
                abs_ydiff = min(abs(y1-y2) for y1 in same for y2 in same if y1 != y2)
                res = min(res, abs_ydiff*abs(x_idxes[q]-x_idxes[i]))
        return res if flag else 0

思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******

对角线的思路，

我们先把所有的点都放进一个字典里面

然后做两次循环，只看从左下到右上的对角线，即(x1, y1)为rectangke的左下角的点，(x2, y2)为rectangke的右上角的点，为什么要这样确定一下呢， 因为我们一共要做两次循环，如果左下到右上的对角线可以成立，那么只要他对应的另外一条对角线上的两个点存在的话我们是一定可以遍历到他们的组合的，也就是说我们这样相当于就是重复计算了，所以我们只要求左下到右上的对角线就行了，相应的，如果只求左上到右下的对角线也是可以的。

class Solution:
    def minAreaRect(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        lookup = {}
        for p in points:
            x, y = p
            lookup[(x,y)] = 1
        res = sys.maxsize
        for i, p1 in enumerate(points):
            x1, y1 = p1 # 左下角的点
            for j, p2 in enumerate(points):
                x2, y2 = p2 # 右上角的点
                if not (x1 < x2 and y1 < y2): # 如果不满足左下到右上对角线，就continue
                    continue
                if (x1, y2) in lookup and (x2, y1) in lookup: # 对应的另外一条左上到右下对角线存在
                    res = min(res, (y2-y1)*(x2-x1))
        return res if res != sys.maxsize else 0