golang 解法, 执行用时: 180 ms, 内存消耗: 6.7 MB, 提交时间: 2023-06-01 10:18:35

type pair struct {
	x, y int
}

func minAreaRect(points [][]int) int {
	mp := map[pair]struct{}{}
	for i := range points {
		mp[pair{points[i][0], points[i][1]}] = struct{}{}
	}
	res := math.MaxInt64
	for i := range points {
		for j := i + 1; j < len(points); j++ {
			if points[i][0] == points[j][0] || points[i][1] == points[j][1] {
				continue
			}
			_, a := mp[pair{points[i][0], points[j][1]}]
			_, b := mp[pair{points[j][0], points[i][1]}]
			if a && b {
				area := getArea(points[i], points[j])
				if area < res {
					res = area
				}
			}
		}
	}
	if res == math.MaxInt64 {
		return 0
	}
	return res
}
func getArea(a, b []int) int {
	x := a[0] - b[0]
	if x < 0 {
		x *= -1
	}
	y := a[1] - b[1]
	if y < 0 {
		y *= -1
	}
	return x * y
}

python3 解法, 执行用时: 1292 ms, 内存消耗: 16.3 MB, 提交时间: 2023-06-01 10:18:06

class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        n = len(points)

        rec_set = set() #为了加速查找，以空间换取时间
        for [x,y] in points:
            rec_set.add((x,y))
        
        ######## 用对角线，往前探的思想，是因为可以计算。比暴力遍历要好很多。 有计算的（有目的地搜） 好于 暴力搜（漫无目的地搜）
        res = float('inf')
        for i in range(n):
            [x1, y1] = points[i]
            for j in range(i + 1, n):
                [x2, y2] = points[j]
                if x1 != x2 and y1 != y2:   #不在同行或者同列，可以构成对角线
                    p3 = (x1, y2)
                    p4 = (x2, y1)
                    if p3 in rec_set and p4 in rec_set:     #往前探的思想
                        cur = abs(x1 - x2) * abs(y1 - y2)   #当前的面积
                        res = min(res, cur)
        return 0 if res == float('inf') else res

javascript 解法, 执行用时: 200 ms, 内存消耗: 46 MB, 提交时间: 2023-06-01 10:17:35

/**
 * @param {number[][]} points
 * @return {number}
 */
var minAreaRect = function(points) {
    // 1. map;
    // 2. 左下、右上枚举
    points.sort((a,b) => a[0] - b[0]);
    let m = new Map();
    let res = Infinity;
    for (let [x,y] of points) {
        if (!m.has(x)) m.set(x, new Set());
        m.get(x).add(y);
    }
    for (let i=0; i<points.length-1; i++) {
        for (let j=i+1; j<points.length; j++) {
            let [x1,y1] = points[i];
            let [x2,y2] = points[j];
            if (x1 < x2 && y1 < y2) {
                // [x1, y2], [x2, y1]
                if (m.get(x1).has(y2) && m.get(x2).has(y1)) {
                    res = Math.min(res, (x2-x1)*(y2-y1));
                }
            }
        }
    }
    return res === Infinity ? 0 : res;
};

java 解法, 执行用时: 140 ms, 内存消耗: 42.4 MB, 提交时间: 2023-06-01 10:17:00

// 枚举对角线
class Solution {
    public int minAreaRect(int[][] points) {
        Set<Integer> pointSet = new HashSet();
        for (int[] point: points)
            pointSet.add(40001 * point[0] + point[1]);

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < points.length; ++i)
            for (int j = i+1; j < points.length; ++j) {
                if (points[i][0] != points[j][0] && points[i][1] != points[j][1]) {
                    if (pointSet.contains(40001 * points[i][0] + points[j][1]) &&
                            pointSet.contains(40001 * points[j][0] + points[i][1])) {
                        ans = Math.min(ans, Math.abs(points[j][0] - points[i][0]) *
                                            Math.abs(points[j][1] - points[i][1]));
                    }
                }
            }

        return ans < Integer.MAX_VALUE ? ans : 0;
    }
}

python3 解法, 执行用时: 1548 ms, 内存消耗: 16.2 MB, 提交时间: 2023-06-01 10:16:30

class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        # 枚举对角线
        S = set(map(tuple, points))
        ans = float('inf')
        for j, p2 in enumerate(points):
            for i in range(0, j):
                p1 = points[i]
                if (p1[0] != p2[0] and p1[1] != p2[1] and
                        (p1[0], p2[1]) in S and (p2[0], p1[1]) in S):
                    ans = min(ans, abs(p2[0] - p1[0]) * abs(p2[1] - p1[1]))
        return ans if ans < float('inf') else 0

python3 解法, 执行用时: 608 ms, 内存消耗: 33.8 MB, 提交时间: 2023-06-01 10:15:12

class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        columns = collections.defaultdict(list)
        for x, y in points:
            columns[x].append(y)
        lastx = {}
        ans = float('inf')

        for x in sorted(columns):
            column = columns[x]
            column.sort()
            for j, y2 in enumerate(column):
                for i in range(0, j):
                    y1 = column[i]
                    if (y1, y2) in lastx:
                        ans = min(ans, (x - lastx[y1,y2]) * (y2 - y1))
                    lastx[y1, y2] = x
        return ans if ans < float('inf') else 0

java 解法, 执行用时: 160 ms, 内存消耗: 54.9 MB, 提交时间: 2023-06-01 10:14:37

// 按列排序
class Solution {
    public int minAreaRect(int[][] points) {
        Map<Integer, List<Integer>> rows = new TreeMap();
        for (int[] point: points) {
            int x = point[0], y = point[1];
            rows.computeIfAbsent(x, z-> new ArrayList()).add(y);
        }

        int ans = Integer.MAX_VALUE;
        Map<Integer, Integer> lastx = new HashMap();
        for (int x: rows.keySet()) {
            List<Integer> row = rows.get(x);
            Collections.sort(row);
            for (int i = 0; i < row.size(); ++i)
                for (int j = i+1; j < row.size(); ++j) {
                    int y1 = row.get(i), y2 = row.get(j);
                    int code = 40001 * y1 + y2;
                    if (lastx.containsKey(code))
                        ans = Math.min(ans, (x - lastx.get(code)) * (y2-y1));
                    lastx.put(code, x);
                }
        }

        return ans < Integer.MAX_VALUE ? ans : 0;
    }
}