LeetCode 939. 最小面积矩形（哈希）
LeetCode 939. 最小面积矩形（哈希）
Michael阿明
发布于 2021-02-19 11:18:08
发布于 2021-02-19 11:18:08
文章被收录于专栏：Michael阿明学习之路
文章目录
1. 题目
给定在 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 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
所有的点都是不同的。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-area-rectangle 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 枚举4个顶点是会超时的
- 枚举对角线组合，然后在哈希里检查另外两个顶点是否都存在
class Solution {
public:
int minAreaRect(vector<vector<int>>& points) {
int i, j, area = INT_MAX, s;
unordered_map<int, unordered_set<int>> m;
for(auto& p : points)
m[p[0]].insert(p[1]);
for(i = 0; i < points.size(); ++i)
for(j = i+1; j < points.size(); ++j)
{
if(points[i][0]==points[j][0] || points[i][1]==points[j][1]
|| !m[points[i][0]].count(points[j][1]) || !m[points[j][0]].count(points[i][1]))
//i,j作为对角线，另外两点不存在
continue;
s = abs(points[i][0]-points[j][0])*abs(points[i][1]-points[j][1]);
if(s < area)
area = s;
}
return area==INT_MAX ? 0 : area;
}
};1316 ms 18.8 MB
- 根据题目的数据范围，哈希采用40001进制数，压缩为一个int，加快运行速度
class Solution {
public:
int minAreaRect(vector<vector<int>>& points) {
int i, j, area = INT_MAX, s;
unordered_set<int> m;
for(auto& p : points)
m.insert(p[0]*40001+p[1]);
for(i = 0; i < points.size(); ++i)
for(j = i+1; j < points.size(); ++j)
{
if(points[i][0]==points[j][0] || points[i][1]==points[j][1]
|| !m.count(points[i][0]*40001+points[j][1]) || !m.count(points[j][0]*40001+points[i][1]))
//i,j作为对角线，另外两点不存在
continue;
s = abs(points[i][0]-points[j][0])*abs(points[i][1]-points[j][1]);
if(s < area)
area = s;
}
return area==INT_MAX ? 0 : area;
}
};832 ms 17.1 MB
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/08/17 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
