Leetcode 939 Minimum Area Rectangle

发表于 |

给定在 xy 平面上的一组点，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。
如果没有任何矩形，就返回 0。

示例 1：
输入：[[1,1],[1,3],[3,1],[3,3],[2,2]]
输出：4
示例 2：
输入：[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
输出：2

提示：

  1. 1 <= points.length <= 500
  2. 0 <= points[i][0] <= 40000
  3. 0 <= points[i][1] <= 40000
  4. 所有的点都是不同的。

题意分析：
在所有点中找出四个点，使其能够构成一个平行于坐标轴的矩形，求可能构成的矩形的最小面积。

思路分析：
我们先用两个字典将所有的点按照横坐标和纵坐标记录下来
我们用dx[i]表示在x= i这条线上的所有点的纵坐标，用dy[i]表示在y=i这条线上所有点的纵坐标，那么对于示例1:，有：
dx = {1: [1,3], 2:[2], 3:[1,3]}
dy = {1: [1,3], 2:[2], 3:[1,3]}

我们如何去寻找矩形的四个点呢？

  1. 在dx中选定一个x
  2. 在dx[x]中选定两个不同的y，分别为y1,y2
  3. 在dy[y1]中找到一个x1，且 x1 != x
  4. 最后判断 x1,y2 是否存在于points当中。
  5. 若存在，计算面积
  6. 若不存在，go to step 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 2000ms
import collections
def minAreaRect(points):
    s = set(map(tuple, points))
    dx = collections.defaultdict(list)
    dy = collections.defaultdict(list)
    for x,y in points:
        dx[x].append(y)
        dy[y].append(x)

    res = float('inf')
    # 1. 确定x
    for x in sorted(dx.keys()):
        # 2.确定y1
        for i in range(len(dx[x])):
            y1 = dx[x][i]
            # 确定y2
            for j in range(i+1, len(dx[x])):
                y2 = dx[x][j]
                # 3. 寻找x1
                for x1 in dy[y2]:
                    if x1 == x: continue
                    # 4. 判断(x1,y1)是否在points当中
                    if (x1, y1) in s:
                        res = min(res, abs(x-x1) * abs(y1-y2))

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

你可能会有疑问，怎么耗时这么长，那是因为会有重复计算，就比如上图中，选择x的时候作为第一步的基准的时候将这个矩形考虑了一次，选择x1作为第一步的时候又将这个矩形计算了一次，这样就会存在大量重复计算，那怎么修改呢？

关键在于我们始终选择第一步中的x作为矩形左边这条边，之后寻找的x1必须要比x大才行。
只要将if x1 == x 改为 if x1 <= x即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 1300ms
import collections
def minAreaRect(points):
    s = set(map(tuple, points))
    dx = collections.defaultdict(list)
    dy = collections.defaultdict(list)
    for x,y in points:
        dx[x].append(y)
        dy[y].append(x)

    res = float('inf')
    for x in sorted(dx.keys()):
        for i in range(len(dx[x])):
            y1 = dx[x][i]
            for j in range(i+1, len(dx[x])):
                y2 = dx[x][j]
                for x1 in dy[y2]:
                    if x1 <= x: continue
                    if (x1, y1) in s:
                        res = min(res, abs(x-x1) * abs(y1-y2))

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