【leetcode】939. Minimum Area Rectangle

题目如下：

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.

解题思路：题目中约定了矩形的各边要与X轴或者Y轴平行，所以不妨把所有的点按X轴进行分组。例如 [[1,1],[1,3],[3,1],[3,3],[2,2]]，以X的坐标分组后得到 {1: [1, 3], 2: [2], 3: [1, 3]}，接下来只要判断两个不同的X轴所对应的Y轴的list中是否存在相同的元素，如果相同则表示可以组成一个题目中要求的矩形。最后求出最小面积即可。

代码如下：

class Solution(object):

    def minAreaRect(self, points):

        """

        :type points: List[List[int]]

        :rtype: int

        """

        dic_x = {}

        res = float('inf')

        x_set = set()

        for (x,y) in points:

            dic_x[x] = dic_x.setdefault(x,[]) + [y]

            x_set.add(x)

        x_list = sorted(list(x_set))

        for kx1 in range(len(x_list)):

            for kx2 in range(kx1+1,len(x_list)):

                intersection = sorted((list(set(dic_x[x_list[kx1]]) & set(dic_x[x_list[kx2]]))))

                if len(intersection) < 2:

                    continue

                minDis = intersection[-1] - intersection[0]

                for i in range(len(intersection)-1):

                    minDis = min(minDis,intersection[i+1] - intersection[i])

                #print kx1,kx2,intersection

                res = min(res, minDis * abs(x_list[kx1]-x_list[kx2]))

        return res if res != float('inf') else 0

巴特西

【leetcode】939. Minimum Area Rectangle

最新文章

热门文章